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.

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 –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
// Data structure to store a Binary Tree node struct Node { int data; Node *left, *right; }; // Function to check if given node is a leaf node or not bool isLeaf(Node* node) { return (node->left == nullptr && node->right == nullptr); } // Main function to truncate given binary tree to remove nodes // which lie on a path having sum less than k void trunc(Node* &curr, int k, int sum) { // base case: empty tree if (curr == nullptr) return; // update sum of nodes in path from root node to current node sum = sum + (curr->data); // Recursively truncate left and right subtrees trunc(curr->left, k, sum); trunc(curr->right, k, sum); // Since we are doing post-order traversal, it is possible // that subtree rooted at current node is already truncated // and current node is a leaf now // if current node is a leaf node and its path from root node has sum // less than the required sum, remove it if(sum < k && isLeaf(curr)) { // free memory allocated to current node free(curr); // set current node to null (node is passed by reference) curr = nullptr; } } // Function to truncate given binary tree to remove nodes which lie on // a path having sum less than k void truncate(Node* &root, int k) { int sum = 0; trunc(root, k, sum); } |

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