A BST is perfectly balanced if every for every node v number of nodes in the left subtree of v equals number of nodes in the right subtree of v. Given a BST, balance factor of a node V is Height of left subtree of V Height of right subtree of V

(a) Let T be a perfectly balanced BST holding n = 2`1 distinct integers. Give an algorithm to find an element that is smaller than 2`2 1 many elements. What is the run time of your algorithm? Justify the correctness of your algorithm.

(b) Let T be the following BST: the root node is A which has a right subtree G and a left subtree rooted a node B. The node B has a left subtree C and a right subtree rooted at D. The node D has left subtree E and a right subtree F. Suppose that balance factor of A is 2, balance factor of B is 1, balance factor of D is 0. Draw the tree obtained by balancing T. Draw the intermediate trees (if any) obtained while balancing. Once you balance the tree, what are the balance factors of the nodes A, B and D ?