Question

Given an AVL tree show (using pseudocode and/or plain English) how to support the following query called RangeReport(k₁, k₂) which lists all the keys in AVL tree which are in between k₁ and k₂ in O(log n + output) time. (Hint: Think of modifying Inorder).

Answer 1

Algorithm for above problem

void RangeReport(root,k1,k2):
   if(root==null):
       return;
   if(node.data>=k1 and node.data<=k2):
       print(root.data)
       RangeReport(root.left,k1,k2)
       RangeReport(root.right,k1,k2)
   else if(node.data<low):
       RangeReport(root.left,k1,k2)
   else:
       RangeReport(root.right,k1,k2)

Mention in comments if any mistakes or errors are found. Thank you.