## Prune nodes not on paths with given sum

Prune nodes not on paths with given sum is a very commonly asked question in Amazon interviews. It involves two concepts in one problem. First, how to find a path with a given sum and then second, how to prune nodes from binary tree. The problem statement is:

Given a binary tree, prune nodes which are not paths with a given sum.

For example, given the below binary tree and given sum as 43, red nodes will be pruned as they are not the paths with sum 43.

### Prune nodes in a binary tree: thoughts

To solve this problem, first, understand how to find paths with a given sum in a binary tree.  To prune all nodes which are not on these paths,  get all the nodes which are not part of any path and then delete those nodes one by one. It requires two traversals of the binary tree.
Is it possible to delete a node while calculating the path with a given sum? At what point we find that this is not the path with given sum? At the leaf node.
Once we know that this leaf node is not part of the path with given sum, we can safely delete it.  What happens to this leaf node? We directly cannot delete the parent node as there may be another subtree which leads to a path with the given sum. Hence for every node, the pruning is dependent on what comes up from its subtrees processing.

At the leaf node, we return to parent false if this leaf node cannot be part of the path and delete the leaf node. At parent node, we look for return values from both the subtrees. If both subtrees return false, it means this node is not part of the path with the given sum. If one of the subtrees returns true, it means the current node is part of a path with the given sum. It should not be deleted and should return true to its parent.

#### Prune nodes from a binary tree: implementation

```#include<stdio.h>
#include<stdlib.h>
#include<math.h>

struct node{
int value;
struct node *left;
struct node *right;
};
typedef struct node Node;

#define true 1
#define false 0

int prunePath(Node *node, int sum ){

if( !node ) return true;

int subSum =  sum - node->value;
/* To check if left tree or right sub tree
contributes to total sum  */

int leftVal = false, rightVal = false;

/*Check if node is leaf node */
int isLeaf = !( node->left || node->right );

/* If node is leaf node and it is part of path with sum
= given sum return true to parent node so tha parent node is
not deleted */
if(isLeaf && !subSum )
return true;

/* If node is leaf and it not part of path with sum
equals to given sum
Return false to parent node */
else if(isLeaf && subSum ){
free(node);
return false;
}
/* If node is not leaf and there is left child
Traverse to left subtree*/
leftVal = prunePath(node->left, subSum);

/* If node is not leaf and there is right child
Traverse to right subtree*/
rightVal = prunePath(node->right, subSum);

/* This is crux of algo.
1. If both left sub tree and right sub tree cannot lead to
path with given sum,Delete the node
2. If any one sub tree can lead to path with sum equal
to given sum, do not delete the node */
if(!(leftVal || rightVal) ){
free(node);
return false;
}
if(leftVal || rightVal ){
if(leftVal)
node->right = NULL;
if(rightVal)
node->left = NULL;
return true;
}
return true ;
}

void inoderTraversal(Node * root){
if(!root)
return;

inoderTraversal(root->left);
printf("%d ", root->value);
inoderTraversal(root->right);
}
Node *createNode(int value){
Node * newNode =  (Node *)malloc(sizeof(Node));
newNode->value = value;
newNode->right= NULL;
newNode->left = NULL;

return newNode;
}
if(node == NULL){
return createNode(value);
}
else{
if (node->value > value){
}
else{
}
}
return node;
}

/* Driver program for the function written above */
int main(){
Node *root = NULL;
//Creating a binary tree

inoderTraversal(root);
prunePath(root, 65);

printf( "\n");
if( root ){
inoderTraversal(root);
}
return 0;
}

```

The complexity of this algorithm to prune all nodes which are not on the path with a given sum is O(n).

## Paths with sum k

In last post Paths in Binary Search Tree we discussed and solved problem to find all the paths in binary search tree. The next step is to find a specific path with a sum in a binary tree.
Given a number K, find all paths with sum K in Binary tree. For example, if K  = 21, and given below the binary tree, the path will be [10,5,6].

Keep in mind, that there can be more than one path with a given sum. Confirm with the interviewer what does he expects in implementation.

## Thoughts

We already know how to traverse all paths in the binary search tree. All we need now is to qualify those paths if all nodes in path sum up to given number K.

Let’s figure our recursive nature of the problem. At the root level, we are required to find a path with sum K. As soon as we add root in the path, remaining nodes in path need to add up to K – root.value, in either left or right subtree. For example, in the below tree,  at the whole tree level, the sum required is 21.

As we move down, that is root is added to the path, the sum required further is 11 from either left or right subtree. The problem is reduced to a subproblem.

At this point, we cannot go forward with node(19), as the sum required will be reduced to negative. However, we can move down node(5) and the problem is reduced to finding a path with sum 6.

At this point, we have to find a path with sum 6 in the left and right subtree of node(5). On left subtree, add node(1) to the path. Now the problem reduces to finding a path with sum 5 on right and left subtree of node(1). However, there are not subtrees of nodes (1). Hence, path [ 10,5,1 ] is not correct path.

On the other hand, after adding node(6) in the path, the sum required is 0 and also node(6) is a leaf node, hence path [10,5,6] is required path with given sum in the binary search tree.

As we worked out example, we came up with some basic conditions for algorithm.

1. If at any node in path, sum required becomes negative, do not go down the path.
2. If sum required become zero, check if the last node added is leaf node. If yes, then add path to solution.
3. If sum required is greater than zero, and node is leaf node, then that path is not with required sum.

### Show me the paths with sum k implementation

```package com.company.BST;

import java.util.ArrayList;

/**
* Created by sangar on 10.5.18.
*/
public class BinarySearchTree {

/*   public class Node {
private int value;
private  Node left;
private Node right;

public Node(int value) {
this.value = value;
this.left = null;
this.right = null;
}
}
*/

private void pathWithGivenPath(Node root, int sum,
ArrayList<Integer> path, List<List<Integer> res){
if(root == null)
return;

if(sum < 0) return;

int subSum = sum - root.value;

boolean isLeaf = ( root.left == null
&& root.right == null );
if(isLeaf && subSum == 0){
}
pathWithGivenPath(root.left, subSum, path);
pathWithGivenPath(root.right, subSum, path);

path.remove(path.size()-1);
}

public void printPathWithGivenPath(int sum){
ArrayList<Node> path = new ArrayList<>();
pathWithGivenPath(this.root, sum, path);
}
}
```

The complexity of the algorithm to print all paths with a given sum in a binary search tree is O(n) as we will be scanning all nodes of BST at least once.

Please share if there is something wrong or missing. If you want to contribute and share your knowledge with thousands of learners across the world, please reach out to us at [email protected]