Deletion from BST (Binary Search Tree)

Given a BST, write an efficient function to delete a given key in it.

 

To delete a node from BST, there are three possible cases to consider:
 

Case 1: Deleting a node with no children: simply remove the node from the tree.

Deletion from BST case-1

Case 2: Deleting a node with two children: call the node to be deleted N. Do not delete N. Instead, choose either its in-order successor node or its in-order predecessor node, R. Copy the value of R to N, then recursively call delete on R until reaching one of the first two cases. If you choose in-order successor of a node, as right sub tree is not NULL (Our present case is node has 2 children), then its in-order successor is node with least value in its right sub tree, which will have at a maximum of 1 sub tree, so deleting it would fall in one of the first 2 cases.

Deletion from BST

Case 3: Deleting a node with one child: remove the node and replace it with its child.

Deletion from BST case-3

Broadly speaking, nodes with children are harder to delete. As with all binary trees, a node’s in-order successor is its right subtree’s left-most child, and a node’s in-order predecessor is the left subtree’s right-most child. In either case, this node will have zero or one children. Delete it according to one of the two simpler cases above.

C++

Download   Run Code


 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).

 


 

Above solution initially search the key in the BST and also find its parent pointer. We can easily modify the code to recursively search the key in deletion procedure itself and let recursion take care of updating the parent pointer.

C++

Download   Run Complete Code


 
The time complexity of above solution is O(n).

 
Insertion in BST

Searching in BST

 
References:https://en.wikipedia.org/wiki/Binary_search_tree

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
Somil
Guest
Somil

Awesome

krishna kumar
Guest
krishna kumar
In Case 2 picture, after deleting the 20 node and put across the 16 node in place of 20 node, it made tree not BST, i believe 20 node must be replace with 19 so that left node would always be less than the immediate parent node and right node… Read more »
wpDiscuz