Binary Search Trees C#


Trees are another well known data structure. Again, they use the Node object and basically, a tree node will always one root node that has a link to 2 other nodes (usually left and right) and then when the tree grows in size, the left or right nodes become parent nodes. To illustrate:

So in the diagram(s) above, we see that there will always be one node that acts as the root node (a node that is considered to be the starting point, so no parent nodes for the root) to the child nodes (left and right), and when there are more items added onto the tree, those child nodes becomes parent nodes and so forth. They can have a reference to either 1 child node or two. These are called binary trees. There’s other kinds of trees, but for now, we will focus on this kind, as they are most commonly used.

Trees are useful in that you can use them to create a mock system directory/folder hierarchy of sorts. Or you just use them to sort your data out. Printing a tree structure requires some recursion because we want to access all the nodes of the tree, so going up and down the tree requires it. Best case scenario, they have O(log(n)) complexity when you’re doing searching through a binary tree, due to the depth and ‘N’ number of items in the tree.

Further animation/example in Java applet of a BST: http://www.ibr.cs.tu-bs.de/courses/ss98/audii/applets/BST/BST-Example.html

My implementation in C# (again this code is very similar in Java):

    class TreeNode
    {
        public int data;
        public TreeNode left { get; set; }
        public TreeNode right { get; set; }

        public TreeNode(int data)
        {
            this.data = data;
        }
    }
    class Tree
    {
        public TreeNode root;//this is public so we can access this treenode from main when we display our tree using the recursive function

        public Tree()
        {
            root = null;
        }
        public void insert(int data)
        {
            TreeNode newItem = new TreeNode(data);//our new node to insert into the tree
            if (root == null)//if theres no root, make the first new node the root
            {
                root = newItem;
            }
            else
            {
                TreeNode current = root;//we make a new treenode called current and assign to the root, so we start iteration from there

                TreeNode parent = null;
                while (current != null)//while the current is not equal to null (since we have it equal to root)
                {
                    parent = current;//set the parent node to point to current (which the root treenode, which will be the parent to the new item treenode)

                    if (data < current.data)
                    //if new item (data) is less than the current node's data, link it to the left node
                    {
                        current = current.left;
                        if (current == null)//if the current.left is null
                        {
                            parent.left = newItem;//make parent.left store the new node
                        }
                    }
                    else
                    {
                        current = current.right;
                        if (current == null)
                        {
                            parent.right = newItem;
                        }
                    }
                }
            }
        }
        public void InOrderRecursiveTreeDisplay(TreeNode root)
        {
            if (root != null)
            {
                InOrderRecursiveTreeDisplay(root.left);
                Console.Write("({0})", root.data);
                InOrderRecursiveTreeDisplay(root.right);
            }
        }
        public bool RecursiveFindValue(TreeNode root, int data)
        {
            if (root != null)
            {
                RecursiveFindValue(root.left, data);
                RecursiveFindValue(root.right, data);
                if (root.data == data)
                {
                    Console.WriteLine("Value exists!");
                    return true;
                }
            }
            return false;
        }
        private TreeNode GoToTarget(int target)//method will return target node
        {
            TreeNode c = root;
            TreeNode returnThis = null;
            while (c != null)
            {
                if (target < c.data)
                {
                    c = c.left;
                }
                if (target == c.data)
                {
                    returnThis = c;
                    break;
                }
                if (target > c.data)
                {
                    c = c.right;
                }
            }
            return returnThis;
        }
        private TreeNode ParentOfTarget(TreeNode target)
        {
            //this method will return the parent node of the target node
            TreeNode current = root;
            TreeNode parent = null;
            while (current != null)
            {
                if (current.left == target || current.right == target)
                {
                    parent = current;
                    break;
                }
                if (target.data < current.data && current.left != target)
                {
                    current = current.left;
                }
                if (target.data > current.data && current.right != target)
                {
                    current = current.right;
                }
            }
            return parent;
        }
        public bool find(int target)
        {
            if (root != null && regular_find(target) != false)
            {
               return true;
            }
            else
                 { return false; }
        }
        private bool regular_find(int target)
        {
            bool isFound = false;
            TreeNode current = root;
            while (current != null && isFound == false)
            {
                if (current.data == target)
                {
                    isFound = true;
                }
                if (target < current.data)
                {
                    if (current.left == null)
                    {
                        break;
                    }
                    else
                    {
                        current = current.left;
                    }
                }
                if (target > current.data)
                {
                    if (current.right == null)
                    {
                        break;
                    }
                    else
                    {
                        current = current.right;
                    }
                }
            }
            if (isFound == true)
            {
                Console.WriteLine("Found it!");
                return true;
            }
            else
            {
                Console.WriteLine("Nope, DNE");
                return false;
            }
        }
    }

       public void Remove(int target)
        {
            if (root == null || find(target) == false)//before we can remove, check to see if it exists
            {
                Console.WriteLine("Value not found to delete!");
                return;
            }
            else
            {
                Console.WriteLine("{0} was removed from the tree", Private_Remove(target));//Private Remove method called here
                return;
            }
        }
 private int Private_Remove(int target)//private remove method does all work, returns the integer value removed
        {
            int temp;
            TreeNode targetNode = GoToTarget(target);
            //case 1, removing the root
            if (targetNode == root)
            {
                if (targetNode.left == null && targetNode.right == null)
                {
                    temp = root.data;
                    root = null;
                    return temp;
                }
                if (targetNode.left != null)
                {
                    //replace top with left if a left-right node dne, else go far right as possible
                    //delete left
                    TreeNode current = root.left;

                    temp = root.data;
                    if (root.left.right == null)//if theres no right child of the left child...
                    { root.data = root.left.data; }
                    else //if there is, we go left and then far right until...
                    {
                        while (current != null)
                        { //we replace the root node with 2nd highest value
                            if (current.right.right == null)
                            { root.data = current.right.data; break; }
                            current = current.right;
                        }
                        if (current.right != null) { current.right = current.right.right; }//works
                        else { current.right = null; }
                        return temp;
                    }

                    if (root.left.left == null)
                    {
                        root.left = null;
                    }
                    else { root.left = root.left.left; }
                    return temp;
                }
                if (targetNode.right != null)
                {
                    temp = root.data;
                    root.data = root.right.data;
                    if (root.right.right == null)
                    {
                        root.right = null;
                    }
                    else { root.right = root.right.right; }
                    return temp;
                }
            }
            
            //case 2 , removing nonroot
            if (targetNode.left == null && targetNode.right == null)
            {//target has no children
                if (ParentOfTarget(targetNode).left == targetNode)
                {
                    temp = targetNode.data;
                    ParentOfTarget(targetNode).left = null;
                }
                else
                {
                    temp = targetNode.data;
                    ParentOfTarget(targetNode).right = null;
                }
                return temp;
            }
            //target has 1 child
            if (targetNode.left != null && targetNode.right == null)
            {
                temp = targetNode.data;
                ParentOfTarget(targetNode).right = targetNode.left;
                //ParentOfTarget(targetNode).left = targetNode.left;//HERE
                    return temp;
                
            }
            if (targetNode.right != null && targetNode.left == null)
            {
                temp = targetNode.data;
                //here if parent is the root, make it left = target->right
                if (ParentOfTarget(targetNode) == root)
                {
                    ParentOfTarget(targetNode).left = targetNode.right;
                }
                else
                    ParentOfTarget(targetNode).right = targetNode.right;
                    
                return temp;
                
            }
            //target node has 2 children
            if (targetNode.left != null && targetNode.right != null)
            {
                if (ParentOfTarget(targetNode).left == targetNode)
                {
                    //take child.left and replace target
                    temp = targetNode.data;
                    targetNode.data = targetNode.left.data;
                    targetNode.left = null;
                    return temp;
                }
                else
                {
                    temp = targetNode.data;
                    targetNode.data = targetNode.left.data;
                    //check if left->left not null...
                    if (targetNode.left.left != null)
                    {
                        targetNode.left = targetNode.left.left;
                    }
                    else
                        targetNode.left = null;
                    return temp;
                }
                
            }
            return Int32.MinValue;
        }
}
class Program
 {
 static void Main()
 {

 Tree t = new Tree();

 t.insert(5);
 t.insert(3);
 t.insert(9);
 t.insert(1);
 t.insert(4);
 t.insert(8);
 t.insert(10);

 Console.WriteLine("\nTree (inorder)");
 t.InOrderRecursiveTreeDisplay(t.root);
 Console.WriteLine();
 t.RecursiveFindValue(t.root, 1);

 t.Remove(5);
 t.Remove(77);
 t.Remove(1);
 t.Remove(10);
 Console.WriteLine();
 t.InOrderRecursiveTreeDisplay(t.root);
 Console.ReadLine();
}
Advertisements

3 thoughts on “Binary Search Trees C#

  1. Pingback: AVL Tree in C# | Bits and Pieces of Code

  2. Pingback: Red-Black Tree in C# | Bits and Pieces of Code

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s