Q6. Answer the following questions a) A team of biologists keeps information abo
ID: 3816936 • Letter: Q
Question
Q6. Answer the following questions a) A team of biologists keeps information about DNA structures in an AVL tree using as key the specific weight (an integer) of a structure. The biologists routinely ask questions of the type: "Are there any structures in the tree with specific weights between a and b (both 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 is a key x in the tree such that asx b, and returns false if no such key exits. Describe your algorithm in pseudo-code. b) What (and why) is the time complexity of the algorithm?Explanation / Answer
a) AVL tree is a self balacing Binary search tree. So Inorder traversal of AVL tree will give the elements in the tree in increasing order. So when we will do inorder traversal of the tree, and check if current element satisfies a<= x <= b. If yes then we will return true else false.
Psuedocode:
def printInorder(root):
if (root != NULL):
printInorder(root.left)
if(a <= root.val <= b):
return true
printInorder(root.right)
b) The time complexity of this algorithm will be same as the time complexity of Inorder traversal i.e O(n) where n is the number of nodes in the tree.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.