My Binary Tree Implementation

BinaryTree.cs

 class Program
    {
        static void Main()
        {
            TestBinaryTree();

            Console.ReadKey();
        }

        static void TestBinaryTree()
        {
            const int size = 1000;
            var tree       = new BinaryTree();

            Console.WriteLine("Filling the tree with {0} nodes...", size);

            var watch = Stopwatch.StartNew();
            for (var i = 1; i <= size; i++) tree.Insert(i);
            watch.Stop();

            Console.WriteLine("Done. Took {0} seconds", watch.ElapsedMilliseconds / 1000.0);
            Console.WriteLine();


            Console.WriteLine("Traversing all {0} nodes in tree...", size);

            watch = Stopwatch.StartNew();

            foreach (var _ in tree.Traverse(tree.Root))
            {}
            watch.Stop();

            Console.WriteLine("Done. Took {0} seconds", watch.ElapsedMilliseconds / 1000.0);
            Console.WriteLine();

            tree.Display();
            tree.Balance();
            tree.Display();

            foreach (var node in tree.Traverse(tree.Root))
            {
                //Console.WriteLine(Environment.NewLine);
                //Console.WriteLine(node.Value);
            }

            var node5 = tree.Search(5, tree.Root);
        }
    }

    class BinaryTree
    {
        public int Count { get; set; }
        public Node Root { get; set; }

        public BinaryTree()
        {
            
        }

        public Node Insert(int value)
        {
            Count++;
            var newNode = new Node(value);
            var node    = GetLeaf(value, Root);

            if (node == null)
                Root = newNode;
            else if (value > node.Value)
                node.Right = newNode;
            else
                node.Left = newNode;
            return node ?? Root;
        }
            
        public IEnumerable<Node> Traverse(Node node)
        {
            if (node == null)
                yield break;

            yield return node;

            foreach (var leftNode in Traverse(node.Left)) yield return leftNode;
            foreach (var rightNode in Traverse(node.Right)) yield return rightNode;
        }

        public Node Search(int value, Node node)
        {   
            if (node == null) return null;
            return value == node.Value ? node : 
                Search(value, value > node.Value ? node.Right : node.Left);
        }

        public Node GetLeaf(int value, Node node)
        {   
            if (node == null) return null;
            return node.IsLeaf() ? node : GetLeaf(value, value > node.Value ? node.Right : node.Left);
        }

        private Node Balance(IReadOnlyList<int> values, int min, int max)
        {
            if (min == max)
                return null;

            var median = min + (max - min) / 2;
            return new Node(values[median])
            {
                Left  = Balance(values, min, median),
                Right = Balance(values, median + 1, max)
            };
        }
         
        public void Balance() => 
            Root = Balance(Traverse(Root).Select(n=> n.Value).ToList(), 0, Count);

        public void Display() => 
            Root.Display("", true);
    }

    class Node
    {
        public int Value;
        public Node Left;
        public Node Right;

        public Node(int value) => Value = value;

        public void Display(string indent, bool last)
        {
            Console.Write(indent);
            if (last)
            {
                Console.Write("└─");
                indent += "  ";
            }
            else
            {
                Console.Write("├─");
                indent += "| ";
            }

            Console.WriteLine(Value);

            var children = new List<Node>();
            if (Left != null)
                children.Add(Left);
            if (Right != null)
                children.Add(Right);

            for (var i = 0; i < children.Count; i++)
                children[i].Display(indent, i == children.Count - 1);
        }

        public bool IsLeaf() => Left == null && Right == null;
    }