We define an AVL binary search tree to be a tree with the bi

We define an AVL binary search tree to be a tree with the binary search tree property where, for each node in the tree, the height of its children differs by no more than 1. For this problem, assume we have a team of biologists that keep information about DNA sequences in an AVL binary search tree using the specific weight (an integer) of the structure as the key. The biologists routinely ask questions of the type, “Are there any structures in the tree with specific weight between a and b, inclusive?” and they hope to get an answer as soon as possible. Design an efficient algorithm that, given integers a and b, returns true if there exists a key x in the tree such that a x b, and false if no such key exists in the tree. Describe your algorithm in pseudocode and English. What is the time complexity of your algorithm? Explain

Solution

Procedure Search_key(Root, a, b)
   /* Root is the root of the tree */
   /* each node hava three fields such that one key field,
       one right child field and one left child field */
  
   if(Root == Null) //check whether root exists or not
  
       return False;
  
   End_if
  
   if(Root->key >= a and Root->key <= b)//check whether key value of root is in range
      
       return True;
      
   else if(Root->key < a)//check whether key value of root is lesser than a
  
       Search_key(Root->rigth, a, b);
      
   else //check whether key value of root is greater than b
  
       Search_key(Root->left, a, b);
      
   End_if
  
End_Search_key

Initially this procedure checks whether the root is exists or not and if root is not exists then it returns False.

if root exists then checks whether its key value is between a and b and if this is true then returns True

else if key value of root is lesser than a then searches processed in the right subtree of the root

else if key value of root is greater than b then searches processed in the left subtree of the root

This procedure continues until root becomes Null or a match is found

Time Complexity - O(logn) as this algorithm is same as search algorithm for a key in bst as avl tree is also a bst