Prune nodes out of range in a binary search tree

Tags: , , , ,

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.