Truncate 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.

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 –

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.

(1 votes, average: 5.00 out of 5)