Truncate given binary tree to remove nodes which lie on a path having sum less than K

Given a binary tree, a complete path is defined as a path from root to a leaf. The sum of all nodes on that path is defined as the sum of that path. Given a number K, remove nodes from the tree which lie on a path having sum less than K.

 

A node can be part of multiple paths. So we have to delete it only in case when all paths from it have sum less than K.

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

trunc-tree
 


 

The problem might look complex at first look but its solution is very simple. The idea is to traverse the tree in bottom-up fashion and truncate left and right subtree first before processing a node. Since we are doing a post-order 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 sum of nodes in path from root node to current node is more than or equal to K, nothing needs to be done.
  • if is a leaf node and its path from root node has sum less than the K, we remove it

 
C++ implementation –
 

Download   Run Complete Code

 
The time complexity of above solution is O(n) and need O(h) extra space for the call stack where h is the height of the 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
wpDiscuz