Prune nodes not on paths with given sum

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 not on path with given sum
Prune nodes not on path with given sum

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;
}
Node *addNode(Node *node, int value){
	if(node == NULL){
		return createNode(value);
	}
	else{
		if (node->value > value){
			node->left = addNode(node->left, value);
		}
		else{
			node->right = addNode(node->right, value);
		}
	}
	return node;
}

/* Driver program for the function written above */
int main(){
	Node *root = NULL;
	//Creating a binary tree
	root = addNode(root,30);
	root = addNode(root,20);
	root = addNode(root,15);
	root = addNode(root,25);
	root = addNode(root,40);
	root = addNode(root,37);
	root = addNode(root,45);
	
	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).

Please share if there is something wrong or missing. If you are preparing for interviews, please signup for free interview material.

Path with given sum in binary search tree

Path with given sum in binary search tree

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

path with given sum in binary search tree

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

Path with given sum : Thoughts

We already know how to traverse all paths in 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 problem. At the root level, we are required to find path with sum K. As soon as we add root in path, remaining nodes in path needs to add up to K – root.value, in either left or right subtree. For example, in below tree,  at whole tree level, sum required is 21.

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

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

path with given sum

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

On the other hand, after adding node(6) in path, sum required is 0 and also node(6) is a leaf node, hence path [10,5,6] is required path with given sum in 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.

Paths with given sum  : Implementation

#include<stdio.h>
#include<stdlib.h>
 
struct node{
	int value;
	struct node *left;
	struct node *right;
};

typedef struct node Node;

void printPath(Node * node, int sum, int path[], int pathLen){
	
	if(!node)
		return;
	
	int subSum = sum - node->value;
	path[pathLen] = node->value;
	
	int isLeaf = !( node->left || node->right );
        if(isLeaf && subSum == 0){
        	printf(" Path with given sum is: " );
	        for(int i=0; i<=pathLen; i++)
               	     printf("%d, ", path[i]);
           	printf("\n");
        }  
        printPath(node->left, subSum, path, pathLen+1);
        printPath(node->right, subSum, path, pathLen+1);
        return ;
}

Node * createNode(int value){
  Node *newNode =  (Node *)malloc(sizeof(Node));
  
  newNode->value = value;
  newNode->right= NULL;
  newNode->left = NULL;
  
  return newNode;
}

Node * addNode(Node *node, int value){
  if(node == NULL){
      return createNode(value);
  }
  else{
     if (node->value > value){
        node->left = addNode(node->left, value);
      }
      else{
        node->right = addNode(node->right, value);
      }
  }
  return node;
}
 
/* Driver program for the function written above */
int main(){
  Node *root = NULL;
  int n = 0;
  //Creating a binary tree
  root = addNode(root,30);
  root = addNode(root,20);
  root = addNode(root,15);
  root = addNode(root,25);
  root = addNode(root,40);
  root = addNode(root,37);
  root = addNode(root,45);
  int path[100];
  printPath(root, 115, path, 0);
  
  return 0;
}

Java implementation

package com.company.BST;

import java.util.ArrayList;

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

    private Node root;

    public void BinarySearchTree(){
        root = null;
    }

    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;
        }
    }

    public void insert(int value){
        this.root =  insertNode(this.root, value);
    }

    private Node insertNode(Node root, int value){
        if(root == null){
            //if this node is root of tree
            root = new Node(value);
        }
        else{
            if(root.value > value){
                //If root is greater than value, node should be added to left subtree
                root.left = insertNode(root.left, value);
            }
            else{
                //If root is less than value, node should be added to right subtree
                root.right = insertNode(root.right, value);
            }
        }
        return root;
    }

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

        if(sum < 0) return;

        int subSum = sum - root.value;
        path.add(root);

        boolean isLeaf = ( root.left == null && root.right == null );
        if(isLeaf && subSum == 0){
            path.forEach(node -> System.out.print(" " + node.value));
            System.out.println();
        }
        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);
    }
}

Test class

package com.company.BST;

/**
 * Created by sangar on 10.5.18.
 */
public class BinarySearchTreeTests {
    public static void main (String[] args){
        BinarySearchTree binarySearchTree = new BinarySearchTree();

        binarySearchTree.insert(7);
        binarySearchTree.insert(8);
        binarySearchTree.insert(6);
        binarySearchTree.insert(9);
        binarySearchTree.insert(3);
        binarySearchTree.insert(4);

        binarySearchTree.printPathWithGivenPath(20);
    }
}

Complexity of algorithm to print all paths with given sum in 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 communications@algorithmsandme.com