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 of 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 in the test results of the implementation.
|
BeforeInsert: ![]()
Insertcall: bst.InsertNode(17);
AfterInsert: ![]() |
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; //Getthe parent
if(tempDelete == tempParent.Left) //Makeparent 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 canhave 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 nodeto the value of to be deleted node
//predNode = null; //Remove predecessornode as it's no longer required.
}
return data + " Deleted";
}
else
return "Please enter the valid tree element!";
} |
The following in the test results of the implementation.
|
Case 1: Thenode has no child.
BeforeDelete:
![]()
Deletecall: Console.WriteLine(bst.DeleteNode(14));
AfterDelete:
![]()
Case 2: Thenode has either a left or right child.
BeforeDelete:
![]()
Deletecall: Console.WriteLine(bst.DeleteNode(45));
AfterDelete:
![]()
Case 3: The node has two children.
BeforeDelete:
![]()
Deletecall: Console.WriteLine(bst.DeleteNode(20));
AfterDelete:
![]()
|