Deletion from BST

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-2-case-1

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++ implementation –
 

Download   Run Code

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


 

Above solution initally 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++ implementation –
 

Download   Run Complete Code

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

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 🙂
 


    

  • Somil

    Awesome