02 May

C# Binary Search Tree Implementation

This example shows how to implement a Binary Search Tree using  C#. A tree whose nodes have at most 2 child nodes is called a binary tree. we name them the left and right child because each node in a binary tree can have only 2 children.
A sample binary tree:
binary tree 2

Tree Traversals (PreOrder, InOrder, PostOrder)

Traversal is a process to visit all the nodes of a tree. In this example, I implemented three method which we use to traverse a tree.

  • PreOrder Traversal
  • InOrder Traversal
  • PostOrder Traversal

PreOrder Traversal:

  • Visit the root
  • Traverse the left subtree
  • Traverse the right subtree

InOrder Traversal:

  • Traverse the left subtree
  • Visit the root
  • Traverse the right subtree

PostOrder Traversal:

  • Traverse the left subtree
  • Traverse the right subtree
  • Visit the root

All source code is below.
Node Class:

        
    class Node
    {
        public Node LeftNode { get; set; }
        public Node RightNode { get; set; }
        public int Data { get; set; }
    }

BinaryTree Class:

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

        public bool Add(int value)
        {
            Node before = null, after = this.Root;

            while (after != null)
            {
                before = after;
                if (value < after.Data) //Is new node in left tree? 
                      after = after.LeftNode; 
                else if (value > after.Data) //Is new node in right tree?
                    after = after.RightNode;
                else
                {
                    //Exist same value
                    return false;
                }
            }

            Node newNode = new Node();
            newNode.Data = value;

            if (this.Root == null)//Tree ise empty
                this.Root = newNode;
            else
            {
                if (value < before.Data)
                    before.LeftNode = newNode;
                else
                    before.RightNode = newNode;
            }

            return true;
        }

        public Node Find(int value)
        {
            return this.Find(value, this.Root);            
        }

        public void Remove(int value)
        {
            this.Root = Remove(this.Root, value);
        }

        private Node Remove(Node parent, int key)
        {
            if (parent == null) return parent;

            if (key < parent.Data) parent.LeftNode = Remove(parent.LeftNode, key); else if (key > parent.Data)
                parent.RightNode = Remove(parent.RightNode, key);

            // if value is same as parent's value, then this is the node to be deleted  
            else
            {
                // node with only one child or no child  
                if (parent.LeftNode == null)
                    return parent.RightNode;
                else if (parent.RightNode == null)
                    return parent.LeftNode;

                // node with two children: Get the inorder successor (smallest in the right subtree)  
                parent.Data = MinValue(parent.RightNode);

                // Delete the inorder successor  
                parent.RightNode = Remove(parent.RightNode, parent.Data);
            }

            return parent;
        }

        private int MinValue(Node node)
        {
            int minv = node.Data;

            while (node.LeftNode != null)
            {
                minv = node.LeftNode.Data;
                node = node.LeftNode;
            }

            return minv;
        }

        private Node Find(int value, Node parent)
        {
            if (parent != null)
            {
                if (value == parent.Data) return parent;
                if (value < parent.Data)
                    return Find(value, parent.LeftNode);
                else
                    return Find(value, parent.RightNode);
            }

            return null;
        }

        public int GetTreeDepth()
        {
            return this.GetTreeDepth(this.Root);
        }

        private int GetTreeDepth(Node parent)
        {
            return parent == null ? 0 : Math.Max(GetTreeDepth(parent.LeftNode), GetTreeDepth(parent.RightNode)) + 1;
        }

        public void TraversePreOrder(Node parent)
        {
            if (parent != null)
            {
                Console.Write(parent.Data + " ");
                TraversePreOrder(parent.LeftNode);
                TraversePreOrder(parent.RightNode);
            }
        }

        public void TraverseInOrder(Node parent)
        {
            if (parent != null)
            {
                TraverseInOrder(parent.LeftNode);
                Console.Write(parent.Data + " ");
                TraverseInOrder(parent.RightNode);
            }
        }

        public void TraversePostOrder(Node parent)
        {
            if (parent != null)
            {
                TraversePostOrder(parent.LeftNode);
                TraversePostOrder(parent.RightNode);
                Console.Write(parent.Data + " ");
            }
        }
    }

Sample Application:

        
            BinaryTree binaryTree = new BinaryTree();

            binaryTree.Add(1);
            binaryTree.Add(2);
            binaryTree.Add(7);
            binaryTree.Add(3);
            binaryTree.Add(10);
            binaryTree.Add(5);
            binaryTree.Add(8);

            Node node = binaryTree.Find(5);
            int depth = binaryTree.GetTreeDepth();

            Console.WriteLine("PreOrder Traversal:");
            binaryTree.TraversePreOrder(binaryTree.Root);
            Console.WriteLine();

            Console.WriteLine("InOrder Traversal:");
            binaryTree.TraverseInOrder(binaryTree.Root);
            Console.WriteLine();

            Console.WriteLine("PostOrder Traversal:");
            binaryTree.TraversePostOrder(binaryTree.Root);
            Console.WriteLine();

            binaryTree.Remove(7);
            binaryTree.Remove(8);

            Console.WriteLine("PreOrder Traversal After Removing Operation:");
            binaryTree.TraversePreOrder(binaryTree.Root);
            Console.WriteLine();

            Console.ReadLine();

Program output:
binary tree output

See Also:
C# Binary Search Example

13 thoughts on “C# Binary Search Tree Implementation

  1. Your implementation doesn’t work because you commented out some of the code on line 12.

    It should be:

    12:
    if (value after.Data) //Is new node in right tree?
    after = after.RightNode;

    Here is a modified version with the fix, and some additional code for testing:

    /**
    * Original Author Turgay, http://csharpexamples.com/c-binary-search-tree-implementation/
    * Modified by Paul Mehta 2019/11/05
    **/
    using System;
    using System.Collections.Generic;

    namespace InterviewPrep
    {
    public class BinaryTreeTest
    {
    static void TestBinaryTree(int[] values)
    {
    BinaryTree bt = new BinaryTree(values);
    Console.WriteLine(” Depth: ” + bt.GetTreeDepth());

    bt.TraverseInOrder();
    bt.TraversePreOrder();
    bt.TraversePostOrder();

    if (values.Length >= 2)
    {
    Console.WriteLine(” Removing value { ” + values[1] + ” }”);
    bt.Remove(values[1]);
    bt.TraverseInOrder();
    bt.TraversePreOrder();
    bt.TraversePostOrder();
    }

    Console.WriteLine(“\n”);
    }

    public static void Main(string[] args)
    {
    int[] arr1 = { 1, 2, 7, 3, 10, 5, 8, 8, 9 };
    int[] arr2 = { 1, 3, 6, 2, 7, 5, 4, 8, 9 };
    int[] arr3 = { -10, 10, -20, 0, 17, 19, 4, 8, 9, -30, -5 };

    TestBinaryTree(arr1);
    TestBinaryTree(arr2);
    TestBinaryTree(arr3);

    Console.ReadLine();
    }

    }

    class Node
    {
    public Node LeftNode { get; set; }
    public Node RightNode { get; set; }
    public int Data { get; set; }
    }

    class BinaryTree
    {
    public BinaryTree()
    {

    }

    public BinaryTree(int[] values)
    {
    Console.WriteLine(“BinaryTree { ” + string.Join(“,”, values) + ” }”);

    foreach (int i in values)
    {
    Add(i);
    }
    }

    public Node Root { get; set; }

    public bool Add(int value)
    {
    Node before = null, after = this.Root;

    while (after != null)
    {
    before = after;
    if (value after.Data) //Is new node in right tree?
    after = after.RightNode;
    else
    {
    //Exist same value
    return false;
    }
    }

    Node newNode = new Node();
    newNode.Data = value;

    if (this.Root == null)//Tree ise empty
    this.Root = newNode;
    else
    {
    if (value < before.Data)
    before.LeftNode = newNode;
    else
    before.RightNode = newNode;
    }

    return true;
    }

    public Node Find(int value)
    {
    return this.Find(value, this.Root);
    }

    public void Remove(int value)
    {
    Remove(this.Root, value);
    }

    private Node Remove(Node parent, int key)
    {
    if (parent == null) return parent;

    if (key parent.Data)
    parent.RightNode = Remove(parent.RightNode, key);

    // if value is same as parent’s value, then this is the node to be deleted
    else
    {
    // node with only one child or no child
    if (parent.LeftNode == null)
    return parent.RightNode;
    else if (parent.RightNode == null)
    return parent.LeftNode;

    // node with two children: Get the inorder successor (smallest in the right subtree)
    parent.Data = MinValue(parent.RightNode);

    // Delete the inorder successor
    parent.RightNode = Remove(parent.RightNode, parent.Data);
    }

    return parent;
    }

    private int MinValue(Node node)
    {
    int minv = node.Data;

    while (node.LeftNode != null)
    {
    minv = node.LeftNode.Data;
    node = node.LeftNode;
    }

    return minv;
    }

    private Node Find(int value, Node parent)
    {
    if (parent != null)
    {
    if (value == parent.Data) return parent;
    if (value < parent.Data)
    return Find(value, parent.LeftNode);
    else
    return Find(value, parent.RightNode);
    }

    return null;
    }

    public int GetTreeDepth()
    {
    return this.GetTreeDepth(this.Root);
    }

    private int GetTreeDepth(Node parent)
    {
    return parent == null ? 0 : Math.Max(GetTreeDepth(parent.LeftNode), GetTreeDepth(parent.RightNode)) + 1;
    }

    public void TraversePreOrder()
    {
    Console.Write(" Traverse Pre Order: \t");
    TraversePreOrder(this.Root);
    Console.WriteLine();
    }
    public void TraversePreOrder(Node parent)
    {
    if (parent != null)
    {
    Console.Write(parent.Data + " ");
    TraversePreOrder(parent.LeftNode);
    TraversePreOrder(parent.RightNode);
    }
    }

    public void TraverseInOrder()
    {
    Console.Write(" Traverse In Order: \t");
    TraverseInOrder(this.Root);
    Console.WriteLine();
    }
    public void TraverseInOrder(Node parent)
    {
    if (parent != null)
    {
    TraverseInOrder(parent.LeftNode);
    Console.Write(parent.Data + " ");
    TraverseInOrder(parent.RightNode);
    }
    }

    public void TraversePostOrder()
    {
    Console.Write(" Traverse Post Order: \t");
    TraversePostOrder(this.Root);
    Console.WriteLine();

    }
    public void TraversePostOrder(Node parent)
    {
    if (parent != null)
    {
    TraversePostOrder(parent.LeftNode);
    TraversePostOrder(parent.RightNode);
    Console.Write(parent.Data + " ");
    }
    }
    }

    }

  2. I have small doubt about the code,
    when you assign condition, for Root node. on line 26

    if (this.Root == null)//Tree is empty
    this.Root = newNode;

    this does not have properties of RightNode or LeftNode Object which is null.
    So the program will crash on second iteration, because when you check on line 12 the object of afterLeftNode is NULL

    if (value after.Data) //Is new node in right tree?
    after = after.RightNode;

    another question should ask also, is it the root is purposely not define
    the LeftNode or RightNode
    ?

  3. Thank you so much for your code. It is really helpful.
    But there is one major problem.
    The value at the root will never be deleted.
    In your sample, 1 cannot be deleted. Could you fix it please

  4. Hi, thanks so much for the code. Could I ask, how do you print out the depth and whether or not an element is in the tree? (sorry if this seems really basic haha)

  5. This is how I implemented the adding logic(with a little recursion it’s more friendly 🙂 )

    public bool Add(int value)
    {
    var newNode = new Node {Data = value};

    if (Root == null)
    {
    Root = newNode;
    return true;
    }

    return AddChildNode(newNode, Root);
    }

    private bool AddChildNode(Node newNode, Node parent)
    {
    if (newNode.Data > parent.Data)
    {
    if (parent.RightNode == null)
    parent.RightNode = newNode;
    else
    AddChildNode(newNode, parent.RightNode);

    }
    else
    {
    if (parent.LeftNode == null)
    parent.LeftNode = newNode;
    else
    AddChildNode(newNode, parent.LeftNode);
    }

    return true;
    }

Bir yanıt yazın

E-posta adresiniz yayınlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir


8 × dört =