Print BST elements in range K1 and K2

Problem: 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 element of given BST.

Steps:
1) If value of root node is greater than k1, then recursively call in left subtree.
2) If value of root node is smaller than k2, then recursively call in right subtree.
3) If value of root node is in range, then print the root’s value.

Implementation:

/* The function assumes that k1 < k2 */
void printBST(Struct node* node, int k1, int k2)
{
    if(node==NULL) return;
    if(node->data<=k2 && node->data>=k1)
    {   
       printf("%d", node->data);
    }
    else if(node->data < k1)  printBST(node->left, k1, k2);
    else if(node->data > k2)  printBST(node->right, k1, k2);
}

Time Complexity: O(N)
Space Complexity: O(N), for stack trace.

Comments are closed.

Post Navigation