Popular Posts

Wednesday, July 13, 2011

Print BST keys in the given range

Given two values k1 and k2 (where k1 < k2) and a root pointer to a Binary Search Tree. Print all the keys of tree in range k1 to k2. i.e. print all x such that k1<=x<=k2 and x is a key of given BST. Print all the keys in increasing order.
For example, if k1 = 10 and k2 = 22, then your function should print 12, 20 and 22.



Solution:
              Do inorder traversal, if current nodes' data is between K1 and K2 (K1<= root->data  >= K2) Print it.

Time Complexity :   O(log n) + O(k) , where n = no of nodes and k = no of keys printed.

Code:

void printbstkeys(Tnode *root,int k1,int k2)
{
    if(root==NULL)
        return;
    printbstKey(root->left, k1, k2);
    if(root->data >=k1 && root->data <=k2)
        printf(" %d ",root->data);
    printbstKey(root->right,k1,k2);
    return;
}
 
To avoid unwanted traversals we can compare current node's
data with K1 for left subtree and K2 for right subtree.
 
void printbstkeys(Tnode *root,int k1,int k2)
{
    if(root==NULL)
        return;
    if(root->data>=k1)
        printbstKey(root->left, k1, k2);
    if(root->data >=k1 && root->data <=k2)
        printf(" %d ",root->data);
    if(root->data<k2)
        printbstKey(root->right,k1,k2);
    return;
}
 

2 comments:

  1. This comment has been removed by the author.

    ReplyDelete
  2. To increase the efficiency, we can perform a check whether the given range is smaller or larger than root node. In such case we can provide either the left or right child of root as the root node for traversal and going through only left or right sub tree :) :)

    ReplyDelete