Insertion & Deletion in a Binary Search Tree Using C#

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;
               }
           }
        }
    }
}

bst.InsertNode(17);

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: