Binary Search Trees (BSTs) in C#

A Binary Search Tree (also known as a BST) is a data structure that contains ordered nodes. Each node contains an element, a left node and a right node. The nodes on the left are all nodes that contain values lower than the element and the nodes on the right contain values higher than the element.

Binary Search Tree

Nodes can be found very fast, in logarithmic time on average. Suppose you would search for a node with a value of 9 in the above tree. This would take 2 steps.  Searching starts at the root of the tree which is the node with a value of 12.

  1. 9 is smaller than 12 so look in the left subtree
  2. 9 is larger than 7 so look in the right subtree, you’ve found 9!

The below example is a C# console application which illustrates BSTs. Major credits to Mark Allen Weiss for his explanation on BSTs in Data Structures & Problem Solving Using Java.

TreeNode class to represent a node

    class TreeNode<T>
    {
        public T Element { get; set; }
        public TreeNode<T> Left { get; set; }
        public TreeNode<T> Right { get; set; }

        public TreeNode(T element)
        {
            this.Element = element;
        }

        public override string ToString()
        {
            string nodeString = "[" + this.Element + " ";

            // Leaf node
            if (this.Left == null && this.Right == null)
            {
                nodeString += " (Leaf) ";
            }

            if (this.Left != null)
            {
                nodeString += "Left: " + this.Left.ToString();
            }

            if (this.Right != null)
            {
                nodeString += "Right: " + this.Right.ToString();
            }

            nodeString += "] ";

            return nodeString;
        }
    }

BinarySearchTree class to represent a BST

    class BinarySearchTree<T>
    {
        public TreeNode<T> Root { get; set; }

        public BinarySearchTree()
        {
            this.Root = null;
        }

        public void Insert(T x)
        {
            this.Root = Insert(x, this.Root);
        }

        public void Remove(T x)
        {
            this.Root = Remove(x, this.Root);
        }

        public void RemoveMin()
        {
            this.Root = RemoveMin(this.Root);
        }

        public T FindMin()
        {
            return ElementAt(FindMin(this.Root));
        }

        public T FindMax()
        {
            return ElementAt(FindMax(this.Root));
        }

        public T Find(T x)
        {
            return ElementAt(Find(x, this.Root));
        }

        public void MakeEmpty()
        {
            this.Root = null;
        }

        public bool IsEmpty()
        {
            return this.Root == null;
        }

        private T ElementAt(TreeNode<T> t)
        {
            return t == null ? default(T) : t.Element;
        }

        private TreeNode<T> Find(T x, TreeNode<T> t)
        {
            while (t != null)
            {
                if ((x as IComparable).CompareTo(t.Element) < 0)
                {
                    t = t.Left;
                }
                else if ((x as IComparable).CompareTo(t.Element) > 0)
                {
                    t = t.Right;
                }
                else
                {
                    return t;
                }
            }

            return null;
        }

        private TreeNode<T> FindMin(TreeNode<T> t)
        {
            if (t != null)
            {
                while (t.Left != null)
                {
                    t = t.Left;
                }
            }

            return t;
        }

        private TreeNode<T> FindMax(TreeNode<T> t)
        {
            if (t != null)
            {
                while (t.Right != null)
                {
                    t = t.Right;
                }
            }

            return t;
        }

        protected TreeNode<T> Insert(T x, TreeNode<T> t)
        {
            if (t == null)
            {
                t = new TreeNode<T>(x);
            }
            else if ((x as IComparable).CompareTo(t.Element) < 0)
            {
                t.Left = Insert(x, t.Left);
            }
            else if ((x as IComparable).CompareTo(t.Element) > 0)
            {
                t.Right = Insert(x, t.Right);
            }
            else
            {
                throw new Exception("Duplicate item");
            }

            return t;
        }

        protected TreeNode<T> RemoveMin(TreeNode<T> t)
        {
            if (t == null)
            {
                throw new Exception("Item not found");
            }
            else if (t.Left != null)
            {
                t.Left = RemoveMin(t.Left);
                return t;
            }
            else
            {
                return t.Right;
            }
        }

        protected TreeNode<T> Remove(T x, TreeNode<T> t)
        {
            if (t == null)
            {
                throw new Exception("Item not found");
            }
            else if ((x as IComparable).CompareTo(t.Element) < 0)
            {
                t.Left = Remove(x, t.Left);
            }
            else if ((x as IComparable).CompareTo(t.Element) > 0)
            {
                t.Right = Remove(x, t.Right);
            }
            else if (t.Left != null && t.Right != null)
            {
                t.Element = FindMin(t.Right).Element;
                t.Right = RemoveMin(t.Right);
            }
            else
            {
                t = (t.Left != null) ? t.Left : t.Right;
            }

            return t;
        }

        public override string ToString()
        {
            return this.Root.ToString();
        }
    }

The main program

    class Program
    {
        static void Main(string[] args)
        {
            // Initialize a BST which will contain integers
            BinarySearchTree<int> intTree = new BinarySearchTree<int>();

            Random r = new Random(DateTime.Now.Millisecond);
            string trace = "";

            // Insert 5 random integers into the tree
            for (int i = 0; i < 5; i++)
            {
                int randomInt = r.Next(1, 500);
                intTree.Insert(randomInt);
                trace += randomInt + " ";
            }

            // Find the largest value in the tree
            Console.WriteLine("Max: " + intTree.FindMax());

            // Find the smallest value in the tree
            Console.WriteLine("Min: " + intTree.FindMin());

            // Find the root of the tree
            Console.WriteLine("Root: " + intTree.Root.Element);

            // The order in which the elements were added to the tree
            Console.WriteLine("Trace: " + trace);

            // A textual representation of the tree
            Console.WriteLine("Tree: " + intTree);

            Console.ReadLine();

        }
    }

Output:

Max: 452
Min: 17
Root: 245
Trace: 245 432 100 452 17
Tree: [245 Left: [100 Left: [17  (Leaf) ] ] Right: [432 Right: [452  (Leaf) ] ]]

Graphical representation of the resulting BST

Resulting BST

The code belonging to the above example can be downloaded from here.

This entry was posted in C# and tagged , , , , , , , , , , , , , , . Bookmark the permalink. Post a comment or leave a trackback: Trackback URL.

2 Comments

  1. Posted February 26, 2013 at 4:28 pm | Permalink

    How to find the height of the left and right sub tree

    • Posted March 10, 2013 at 10:14 am | Permalink

      Hi Vivian,

      That’s very easy actually, write a method which applies Math.Max to the depths of the left and right subtrees recursively. For example: return Math.Max(left, right). Recursion runs until you find a leaf (node without a left or right child). Each time you perform a recursive call into a subtree, increase the depth by 1.

      I hope this helps you further.

      Regards,

      Ferhat

One Trackback

  1. [...] How to find the subtree height both left and right, I have used this code in the following link C# BSTAny help would be appreciated.Kind Regards This entry was posted in C# and tagged C#, CODE, HEIGHT [...]

Post a Comment

Your email is never published nor shared. Required fields are marked *

*
*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Why ask?