Sunday, April 20, 2014

Prune nodes of binary search tree

This is again a problem which can be easily solved using post order traversal of tree. It fits in to this post:  Binary Search Tree: Trick questions

Problem statement

Given a binary search tree and two integers min and max, prune all nodes of binary search tree which are not in range min and max. 
That is to say 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 
Output will be like output tree.
Input tree
Output tree

Analysis

We need to check each node with min and max and if one condition matches i.e. if root is less than min or root is greater than max, we need to remove that node. However there is a catch here. What happens to its child nodes if root node is removed? To take care of this, we need to process children node before processing the root node. What kind of traversal is that? Yes, it's post order 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 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. So e don't care about left child of node.
Second, right sub tree 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 we need to pass the reference of remaining right sub tree to parent of this node.

2. Node 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 node.

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

Code

Node * prune_nodes(Node * root, int min, int max){

        if(root == NULL) return NULL;

        Node * root->left =  prune_node(root->left, min, max);
        Node * root->right = prune_node(root->right, min, max);

        if(root->value < min)
                Node * right_tree = root->right;
                free(root);
                return right_tree;
        }
        if (root->value > max){
                Node *left_tree = root->left;
                free(root);
                return left_tree;
        }
        return root;
}

Complexity Analysis

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

Blogger Tricks