Trees: Prune Sum Path

Remove all nodes which don’t lie in any path with sum>= k
http://algorithmsandme.in/2014/03/remove-all-nodes-in-binary-tree-which-dont-lie-in-path/

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

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.

1. int prunePath(Node *node, int sum ){
3. if( !node ) return true;
5. int subSum = sum - node->value;
6. /* To check if left tree or right sub tree contributes to total sum */
8. int leftVal = false, rightVal = false;
10. /*Check if node is leaf node */
11. int isLeaf = !( node->left || node->right );
13. /* If node is leaf node and it is part of path with sum = given sum
14. return true to parent node so tha parent node is not deleted */
15. if(isLeaf && !subSum )
16. return true;
18. /* If node is leaf and it not part of path with sum equals to given sum
19.   Return false to parent node */
20. else if(isLeaf && subSum ){
21. free(node);
22. return false;
23. }
24. /* If node is not leaf and there is left child Traverse to left subtree*/
25. leftVal = prunePath(node->left, subSum);
27. /* If node is not leaf and there is right child Traverse to right subtree*/
28. rightVal = prunePath(node->right, subSum);
30. /* This is crux of algo.
31.   1. If both left sub tree and right sub tree cannot lead to path with
32.   given sum,Delete the node
33.   2. If any one sub tree can lead to path with sum equal to given sum,
34.   do not delete the node */
35. if(!(leftVal || rightVal) ){
36. free(node);
37. return false;
38. }
39. if(leftVal || rightVal ){
40. if(leftVal)
41. node->right = NULL;
42. if(rightVal)
43. node->left = NULL;
44. return true;
45. }
46. return true ;
47. }
49. void inoderTraversal(Node * root){
50. if(!root)
51. return;
53. inoderTraversal(root->left);
54. printf("%d ", root->value);
55. inoderTraversal(root->right);
56. }
57. Node *createNode(int value){
58. Node * newNode = (Node *)malloc(sizeof(Node));
59. newNode->value = value;
60. newNode->right= NULL;
61. newNode->left = NULL;
63. return newNode;
64. }
65. Node *addNode(Node *node, int value){
66. if(node == NULL){
67. return createNode(value);
68. }
69. else{
70. if (node->value > value){
71. node->left = addNode(node->left, value);
72. }
73. else{
74. node->right = addNode(node->right, value);
75. }
76. }
77. return node;
78. }

http://codingrecipies.blogspot.com/2014/07/trees-prune-sum-path.html
Bottom - up approach is being used to prune to the tree.

public static boolean prunePath(Node root, int givenSum , int currSum)

{

 if(root==null) {

  if(givenSum==currSum)

   return true;

  else 

   return false;

 }

  

 boolean leftFlag = prunePath(root.left , givenSum , currSum+root.data);

  

 boolean rightFlag = prunePath(root.right , givenSum , currSum+root.data);

  

 if(!leftFlag)

  root.left=null;

 if(!rightFlag)

  root.right=null;

  

 return (leftFlag || rightFlag ) ;//&&?

   

}