Remove nodes from BST that have keys outside the valid range

Given a BST and a valid range of keys, remove nodes from BST that have keys outside the valid range.

 

For example, consider BST shown on the left below. It should be converted to BST shown on the right.

 
remove nodes from BST

 


 

The idea is very simple, we traverse the tree in bottom-up fashion and truncate left and right subtree first before processing a node. Since we are doing a postorder traversal, it is possible that subtree rooted at current node is truncated and current node becomes a leaf node now. So, for each node we check

  • if its key fall within the valid range, nothing needs to be done.
     
  • if root’s key is smaller than the minimum allowed, we remove it and set root to root’s right child
     
  • if root’s key is larger than the maximum allowed, we remove it and set root to root’s left child
     

 
C++ implementation –
 

Download   Run Code

Output:

10 12

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

 
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
wpDiscuz