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

The algorithm for traversing a binary search tree and print elements between k1 and k2 is as below
print_range (TreeRoot r, key k1, key k2):
   if (root is null) return
   if (k2 < k1) return
  
   if (k1 < r.value): // recurse into left subtree
       print_range (r.left, k1, k2)
      
   // Finished recursing left subtree and printing any elements required, check this root node itself  
   if (r.value between k1 and k2):
       print r.value
      
   if (k2 > r.value):   // recurse into right subtree
       print_range (r.right, k1, k2)
      
   return
  
Since the algorithm traverses each node to be printed once (only), if K is the number of elements to be printed, the time taken is O(K). The tree depth is also required to be traversed and the time for that is O(n) where n is the total number of elements. Time for this algorithm is therefore O(K + log n)