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.

Prune nodes out of range in a binary search tree

Prune nodes out of range in a binary search tree

Given a binary search tree and two integers min and max, prune all nodes in binary search tree which are not in range min and max or prune all nodes outside a given range in a binary search tree.  
It means: remove all nodes from BST which are either less than the min or greater than the max.

For example, if for following input tree min = 8 and max = 18 are given 
The output will be like output tree.

prune nodes in bst
Prune nodes in BST
Prune BST
Pruned BST

Prune nodes out of range: thoughts

Check each node with min and max. There are three possibilities: First, the current node is less than the minimum. Second, the current node is greater than the maximum. In these two conditions, we will prune the node. Third, the current node is between the minimum and the maximum.

Let’s discuss the case where a node has to be pruned. What happens to its subtrees if the node is pruned? To decide this, we will process subtrees before processing the current node. What kind of traversal is that? Yes, it’s postorder traversal.

When we are processing a node, there are two cases:
1. Node is less than min. 
In this case we two things for sure. First, all nodes in the left subtree are less than this node and hence less than the minimum. These nodes would have been already deleted when we process left child, remember we are doing postorder traversal so all left subtree is processed before the node. We don’t care about the left subtree of the node.

Second, the right subtree may or may not contain nodes which are less than the minimum, which would have been already pruned and only valid nodes will be remaining. Hence we need to pass the reference of remaining right subtree to the parent of this node.

2. Node is greater than max.
Again in this case too, two things are clear. First, all the nodes on the right subtree are greater than the node and hence greater than the max, so ignore them. They have been already processed anyway, postorder traversal! However, nodes on left subtree may or may not be greater than max, so return the reference to left subtree of the node to its parent before deleting the node.

Prune nodes out of range: implementation

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

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

void inorder( Node * currentNode){
	
	if(!currentNode) return;
	
	inorder(currentNode->left);
	printf("%d ", currentNode->value);
	inorder(currentNode->right);
}

Node * pruneNodes(Node *currentNode, int min, int max){
	
	if(!currentNode) return currentNode;
	
	currentNode->left =  pruneNodes(currentNode->left, min, max);
	currentNode->right = pruneNodes(currentNode->right, min, max);
	if(currentNode->value < min){
		Node * rightTree = currentNode->right;
		free(currentNode);
		
		return rightTree;
	}
	if (currentNode->value > max){
		Node *leftTree = currentNode->left;
		free(currentNode);
		
		return leftTree;
	}
	return currentNode;
}
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){
		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);
        
        inorder(root);
        root = pruneNodes(root, 50,60); 
        printf("\n");
        if(root)
        	inorder(root);
        return 0;
}

Since we are visiting each node of the binary search tree at least once, the complexity of code is O(n) where n is the number of nodes in the binary search tree.

Please share if there is anything wrong or missing. If you are preparing for an interview, please signup to receive free interview preparation material.