In previous posts we learned how to print paths with given sum and print all paths in binary search tree. Today’s problem is to delete all nodes which don’t lie on paths with given sum.

This problem involves two subproblems, one is to find all paths of given sum and second is to remove nodes from tree.

Formally speaking, problem goes like : given a binary tree, defining a term “complete path sum” as, sum of values of nodes lying in a path from root to the leaf; now given a value ‘K’, **find the k-heavy path and prune binary tree i.e. remove nodes which don’t lie on those paths.**

For example, in below tree, if K is given as 65,

resultant tree will look like: 30, 20 and 15

To understand how paths of a given sum are detected in binary search tree, please go through Print paths with given sum in BST. All we have to do is prune all nodes which are not on these paths.

One way is to first get all nodes which are not part of any path and then one by one delete those nodes.

It requires two traversals of tree and as well as space to save all paths. If node can be deleted while calculating paths will save extra traversal ass well the space as path need not be stored anymore.

When is it confirmed that path we are following is not a path with given sum? At leaf node, right?

If a leaf node does not satisfy path condition, it can be deleted.

Now what happens to parent node of leaf node we just deleted? That cannot be deleted as there may be other subtrees of parent node which lead to a path with given sum. For each node, deletion is dependent on what comes from its subtrees.

Well, solution depends on solutions to subproblem, classic case for recursion? What would be base case? If leaf node is not part of path of given sum, delete it and return false indication to parent node. If it is part of path with given sum, return true indication to parent node.

At parent node, there are two possible conditions:

*1. Both left subtree and right subtree return false*

Parent has to be deleted as there is no possible path from this node. Also, return false indication to parent of current node.

*2. Any one subtree returns false*

Then current node cannot be deleted, but we have to appropriately set right or left subtree as NULL.

As we are visiting every node in tree, complexity would be O(N).

Pingback: Amazon interview experience 2 | Algorithms and Me()