Delete a node in Binary Search Tree, easy in 5 minutes

You just have basic knowledge about Binary Search Tree (BST). Now, it’s time to study about delete a node in Binary Search Tree. It is quite different from operations like searching and insertion a node in BST.

Delete a node in Binary Search Tree

There are three cases since doing deletion of a node in Binary Search Tree:

Node to be deleted is leaf

First, you need to search that node then make it null. It is the simplest deletion.

Node to be deleted is leaf, Delete a node in Binary Search Tree

Node to be deleted has only one child

If node have one children then you need to find that deleted node and connect parent of deleted node directly to child of the deleted node.

Delete a node in Binary Search Tree

Node to be deleted has two children

If it has two nodes, we need to connect parent of node to the leftmost node(it is also minimum node) of right subtree or rightmost node(it is also maximum node) of left subtree.

Delete a node in Binary Search Tree

 

Here it is replacing node 20 with node 30. Node 30 is minimum element in right subtree of 20 and deleting node 30.

A complete implementation in Java.

Here is a complete program demonstrate three cases we can delete a node in Binary Search Tree.

Here is output of the above program

Delete a node in Binary Search Tree

Time Complexity

In worst case, you have to travel from root to the deepest leaf node. So time complexity of delete operation is O(h) where h is height of Binary Search Tree.

That’s all about Delete a node in Binary Search Tree tutorial.

References

Binary Search Tree in Java
Binary Tree Java Documentation

Please share it if you found this useful
Hide Buttons