bst - lot of methods, C#

bst - lot of methods

//Title of this code
//Rextester.Program.Main is the entry point for your code. Don't change it.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

namespace Rextester
{
    public class Program
    {
        public static void Main(string[] args)
        {
            Node bst = null;
            Tree.Insert(ref bst, 10);
            Tree.Insert(ref bst, 15);
            Tree.Insert(ref bst, 20);
            Tree.Insert(ref bst, 0);
            Tree.Insert(ref bst, 5);
            
            Console.WriteLine("contains tests:");
            
            Assert(Tree.Contains(bst, 10) == true, "10 exists");
            Assert(Tree.Contains(bst, 4) == false, "4 does not exist");
            Assert(Tree.Contains(bst, 20) == true, "20 exists");
            Assert(Tree.Contains(bst, 0) == true, "0 exists");
            Assert(Tree.Contains(bst, 100) == false, "100 does not exist");
            
            Console.WriteLine("find min tests:");
            
            Assert(Tree.FindMin(bst) == 0, "0 is the minumim");
            
            Console.WriteLine("find max tests:");
            
            Assert(Tree.FindMin(bst) == 20, "20 is the maximum");
            
            Console.WriteLine("level-order traversal - can be used for printing the tree:");
            Tree.LevelOrder(bst);
            
            
            Console.WriteLine();
            Console.WriteLine("pre-order traversal");
            Tree.PreOrder(bst);
            
            
            Console.WriteLine();
            Console.WriteLine("in-order traversal - can be used for sorting the tree:");
            Tree.InOrder(bst);
            
            
            Console.WriteLine();
            Console.WriteLine("post-order traversal");
            Tree.PostOrder(bst);
            
            Console.WriteLine();
            Console.WriteLine("is binary tree?");
            Assert(Tree.IsBinarySearchTree(bst) == true, "this is a binary tree");
            
            
            Console.WriteLine();
            Console.WriteLine("is binary tree? (efficient method)");
            Assert(Tree.IsBinarySearchTreeEfficient(bst) == true, "this is a binary tree");
            
        }
        
        public static void Assert(bool result, string message)
        {
            Console.WriteLine("ASSERT: {0}: {1}", result ? "PASS": "FAIL", message);
        }
        
        public static class Tree
        {
            
            private static Node CreateNode(int data)
            {
               Node root = new Node();
               root.Data = data;
               return root;
            }
         
            
            public static void Insert(ref Node root, int data)
            {
                if (root == null)
                {
                    root = new Node();
                    root.Data = data;
                    Console.WriteLine(root.Data);
                    return;
                }
                
                if (root.Data >= data)
                {
                    if (root.Left == null)
                    {
                        root.Left = new Node();
                        root.Left.Data = data;
                        Console.WriteLine(root.Data);
                    }
                    else
                    {
                        Insert(ref root.Left, data);
                    }
                }
                else
                {
                    if (root.Right == null)
                    {
                        root.Right = new Node();
                        root.Right.Data = data;
                        Console.WriteLine(root.Data);
                    }
                    else
                    {
                        Insert(ref root.Right, data);
                    }
                }
            }
            
            public static bool Contains(Node root, int data)
            {
                if (root == null) return false;
                
                if (root.Data == data) return true;
                
                if (root.Data >= data) 
                {
                    Console.WriteLine(root.Data);
                    return Contains(root.Left, data);
                }
                else
                {
                    Console.WriteLine(root.Data);
                    return Contains(root.Right, data);
                }
            }
            
            public static int FindMin(Node root)
            {
                if (root == null) return -1; //tree is empty
                
                if (root.Left == null) return root.Data; //this is the minumum
                
                return FindMin(root.Left);
            }
            
            
            public static int FindMax(Node root)
            {
                if (root == null) return -1; //tree is empty
                
                if (root.Right == null) return root.Data; //this is the minumum
                
                return FindMin(root.Right);
            }
            
            public static void LevelOrder(Node root)
            {
                if (root == null)
                {
                    Console.WriteLine("Tree is empty.");
                    return;
                }
                
                Queue<Node> printQ = new Queue<Node>();
                
                printQ.Enqueue(root);
                
                while (printQ.Count > 0)
                {
                    Node current = printQ.Dequeue();
                    
                    Console.Write("{0} ", current.Data);
                    
                    if (current.Left != null) printQ.Enqueue(current.Left);
                    
                    if (current.Right != null) printQ.Enqueue(current.Right);
                }
          
                Console.WriteLine();
            }
            
            public static void PreOrder(Node root)
            {
                if (root == null)
                {
                    Console.WriteLine();
                    return;
                }
                
                Console.Write("{0} ", root.Data);
                
                if (root.Left != null) PreOrder(root.Left);
                
                if (root.Right != null) PreOrder(root.Right);
            }
            
            
            public static void InOrder(Node root)
            {
                if (root == null)
                {
                    Console.WriteLine();
                    return;
                }
                
                if (root.Left != null) InOrder(root.Left);
                
                Console.Write("{0} ", root.Data);
                
                if (root.Right != null) InOrder(root.Right);
            }
            
            
            public static void PostOrder(Node root)
            {
                if (root == null)
                {
                    Console.WriteLine();
                    return;
                }
                
                if (root.Right != null) PostOrder(root.Right);
                
                Console.Write("{0} ", root.Data);
            
                if (root.Left != null) PostOrder(root.Left);
            }
            
            public static bool IsBinarySearchTree(Node root)
            {
                if (root == null) return true;
            
                return IsLeftSubTreeLessOrEqual(root.Left, root.Data) && IsRightSubTreeGreater(root.Right, root.Data) && IsBinarySearchTree(root.Left) && IsBinarySearchTree(root.Right);
                
            }
            
            public static bool IsLeftSubTreeLessOrEqual(Node root, int data)
            {
                if (root == null) return true;
                Console.WriteLine("left {0} {1} {2}", root.Data, data, root.Data <= data);
                return root.Data <= data && IsLeftSubTreeLessOrEqual(root.Left, data) && IsLeftSubTreeLessOrEqual(root.Right, data);
            }
            
            public static bool IsRightSubTreeGreater(Node root, int data)
            {
                if (root == null) return true;
                
                Console.WriteLine("right {0} {1} {2}", root.Data, data, root.Data > data);
                return root.Data > data && IsRightSubTreeGreater(root.Left, data) && IsRightSubTreeGreater(root.Right, data);
            }
            
            public static bool IsBinarySearchTreeEfficient(Node node)
            {
                return IsBinarrySearchTreeEfficientInternal(node, int.MinValue, int.MaxValue);
            }
            
            public static bool IsBinarrySearchTreeEfficientInternal(Node node, int min, int max)
            {
                if (node == null) return true;
                
                return node.Data >= min && node.Data < max && IsBinarrySearchTreeEfficientInternal(node.Left, min, node.Data) && IsBinarrySearchTreeEfficientInternal(node.Right, node.Data, max);
            }
        }
        
        public class Node
        {
            public int Data;
            public Node Left;
            public Node Right;   
        }
    }
}


run \| edit \| history \| help	0