Consider a binary search tree with n nodes and height h where: . Every internal node in the tree has exactly two children. (No nodes with only one child.) . For each internal tree node x, the heights of the subtrees rooted at r.left and a.right differ by at most 1 (a) Prove that if the subtree rooted at z has height h', then the heights of the subtrees rooted at r.left and x.right are at least h-2. (Note: One subtree must have height l'1 but the other could have (b) Using your answer to part a), prove that if the binary search tree has height h, then the length of (c) Using your answer to part b), prove that if the binary search tree has height h, then the tree has d) Using your answer to part c), prove that if the binary search tree has n nodes, then the tree has height h -1 or h'-2) the shortest path from the root to any leaf is at least [h/2 at least 2Ih/21+1 -1 nodes. height at most 2 logz(n+1)