Prune nodes of binary search tree

Prune nodes of binary search tree

We discussed problems like delete a binary search tree, mirror a BST or replace node with sum of its children, solution was a post order traversal of tree. In this post, let’s talk about another such problem: Prune nodes from binary search tree which are out of a given range

Prune nodes in binary search tree

Given a binary search tree and range (min and max), prune all nodes from tree which are not in range or remove all nodes from BST which are either less than min or greater than max.
For example, if for following input tree min = 22 and max = 40 are given 

prune nodes of bst

Output will be like below tree:
prune nodes of BST example

For each node, check if node is with in min and max.  If currentNode is less than min or currentNode is greater than max, remove that node. However there is a catch here. What happens to its child nodes of it if currentNode is removed? To take care of this, we need to process children node before processing currentNode. What kind of traversal is that? Yes, post order traversal.
When we are processing currentNode, there are two cases:

currentNode is less than min
In this case, two things for sure. First, all nodes in left sub tree are less than this node and hence less than min. These nodes would have been already deleted when we processes left child. Don’t care about left child of node.

Second, right subtree may or may not contain nodes which are less than min, which would have been already pruned and only valid nodes will be remaining. Hence, pass reference of remaining right subtree to parent of currentNode.

currentNode is greater than max.
Again in this case too, two things are clear. All nodes on right sub tree are greater than node and hence greater than max, so ignore them. They are already processed anyway. However, nodes on left sub tree may or may not be greater than max, so return reference to left sub tree of  node to its parent before deleting the currentNode.

So we process the left child first.Then right child and at last the current node. With above two conditions, decide what has to be returned to parent node of current node.

Algorithm to purge nodes of BST

1. Start with root node, call it currentNode.
2. If there is left child of current node, prune nodes of left sub tree
3. If there is right child of current node, prune nodes of right subtree
4. If value of currentNode is less than minimum,free currentNode and return right subtree to parent node.
5. If value of currentNode is greater than maximum, free currentNode and return left subtree to parent node.
6. If currentNode is within range, return currentNode to parent.
#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;
}

Each node of tree is visited at least once, complexity of algorithm to prune nodes from binary search tree is O(N) where N is number of nodes in BST.

Please share if something is wrong or missing. Sharing is caring. If you are interested in contributing to website, please contact us and earn money.