Question

Given a binary search tree T with n elements. For any two keys k1 and k2 such that k1 < k2, there is an algorithm to print all elements x in T such that k1 ≤x ≤k2 in O(K + log n) time on average, where K is the number of the elements printed out.

Answer 1

Solution

Required algorithm is given below. This algorithm is executed starting from the root node recursively until the condition is false.

Algorithm

if currentNode is not NULL

if k1 < key in currentNode
Left subtree of the currentNode may have some elements in the range between k1 to k2    
Consider the root of the left subtree as current node and follow the algorithm from step 1

if k1 < key in currentNode AND k2>= key
Print the key in currentNode

   if key <= k2 in currentNode
Right subtree of the currentNode may have some elements in the range between k1 to k2. Consider the root of the right subtree as current node and follow the algorithm from step 1

This algorithm requires O(K) to perform the inorder traversal and print K keys. We may have to traverse to the depth of the tree if more number of keys satisfying the condition are found which are proportional to the depth of the tree.   Since the average depth is O(log N), this gives an O(K + log N) average bound.