Insertion & Deletion in a Binary Search Tree Using C#

Binary Search Tree

A Binary Search Tree is a binary tree with a search property where the elements in the left sub-tree are less than the root and elements in the right sub-tree are greater than the root.

For example:

Inserting an element in a BST (Binary Search Tree)

To insert an element in the Binary Search Tree, we first need to find where to insert it. This can be done by traversing left or right as we did for searching for an element.

The following is the /algorithm to do that.

• Check if the root is present or not, if not then it’s the first element.
• If the root is present then we need to find where to insert it.
• Move left or right by comparing until the current node becomes null
• Once the current node becomes null, make it the child of the parent’s node.

The C# implementation of that is as follows.

public void InsertNode (object data)
{
    TNode newNode = new TNode(data);
    if (root.Data == null) //First node insertion
        root = newNode;
    else
    {
       current = root;
       while (true)
       {
           tempParent = current;
           if (Convert.ToInt32(newNode.Data) < Convert.ToInt32(current.Data))
           {
               current = current.Left;
               if(current== null)
               {
                    tempParent.Left =newNode;
                    newNode.Parent =tempParent;
                    return;
                }
           }
           else
           {
               current = current.Right;
               if(current == null)
               {
                    tempParent.Right= newNode;
                    newNode.Parent =tempParent;
                    return;
               }
           }
        }
    }
}

The following is the test results of the implementation.

Before Insert: 

Insert call:

bst.InsertNode(17);

After Insert: 

Deleting an element in a BST (Binary Search Tree)

To delete an element in the Binary Search Tree, we first need to look at the children of it and based on that the method to delete a node is decided. Basically there are three odd cases for deleting a node.

• The node has no children (in other words it’s a leaf node).

• The node has either a left or right child.

• The node has two children.

Now let’s look at each case one by one.

Case 1: The node has no child (in other words it’s a leaf node).

This is the most trivial case where we just need to set the reference of its parent to null.

Case 2: The node has either left or right child.

This is also a simple case where we need to make the children of itself to the children to its parent.

This is similar to how we remove node in Linked List.

Case 3: The node has two children.

This case is a bit tricky (not very difficult though) where we need to move its predecessor (or successor) to it. This involves the following few steps.

• Find the predecessor (or successor) node.

• The Predecessor node can have no or left child, if it has a left child then assign the left child of the predecessor to its parent's right.

• Replace the value of the predecessor node to the value of to be deleted node.

• Optionally, remove the predecessor node since it's no longer required.

The C# implementation of that is as follows.

public object DeleteNode (object data)
{
     TNode tempDelete = this.GetNode(data);
     if (tempDelete != null)
     {
        if ((tempDelete.Left == null ) && (tempDelete.Right == null)) //Its a Leaf node
        {
           tempParent = tempDelete.Parent;
           if(tempDelete == tempParent.Left) //Justremove by making it null
               tempParent.Left = null;
           else
               tempParent.Right = null;
        }
        else if ((tempDelete.Left == null ) ||(tempDelete.Right == null)) //It has either Left orRight child
        {
           tempChild = tempDelete.Left == null? tempDelete.Right : tempDelete.Left; //Get the child
           tempParent = tempDelete.Parent; //Get the parent
           if(tempDelete == tempParent.Left) //Make parent points to it's child so it will automatically deleted like Linked list
               tempParent.Left = tempChild;
           else
               tempParent.Right = tempChild;
          }
          else if ((tempDelete.Left != null) ||(tempDelete.Right != null)) //It has both Left andRight child
         {
            TNodepredNode = this.GetNode(this.TreePredecessor_Ite(data));  //Findit's predecessor
            if(predNode.Left != null) // Predecessor node can have no or left child. Do below two steps only if it has left child
            {
                 tempChild = predNode.Left;
                 predNode.Parent.Right = tempChild; //Assignleft child of predecessor to it's Parent's right.
             }
             tempDelete.Data = predNode.Data; //Replace the value of predecessor node to the value of to be deleted node
                   //predNode = null; //Remove predecessor node as it's no longer required.
         }
         return data + " Deleted";
     }
     else
          return "Please enter the valid tree element!";
}

The following is the test results of the implementation

Case 1: Then node has no child.

BeforeDelete:

Delete call:

Console.WriteLine(bst.DeleteNode(14));

AfterDelete:

Case 2: The node has either a left or right child.

Before Delete:

Delete call:

Console.WriteLine(bst.DeleteNode(45));

After Delete:

 

Case 3: The node has two children.

Before Delete:

Delete call:

Console.WriteLine(bst.DeleteNode(20));

After Delete: