Due date March 5.
For the following questions, write pseudocode, or use the programming language
of your choice. Recall that in either case the most powerful construct in any
language is the comment! That is to say, explain your design.
1. Suppose you are given a sorted array of N numbers. How would you build
a regular binary tree (i.e. one with no additional clever structures) that is
as balanced as possible? Hint: how do you find the best root for the tree?
2. Suppose you have a simple binary tree, where each node holds just a value
and two pointers to child nodes. Write a function or method to determine whether
this tree has the balance property of an AVL tree. As usual, recursion solves
3.Recall that the sparsest AVL tree is one in which every node is as unbalanced
as it can be.
a. What is the number of nodes in the sparsest AVL tree of height 10?
(Formula discussed in class).
b. Write a method that builds the sparsest AVL tree that holds the numbers
1,2...N, where N is the number of nodes of the sparsest AVL tree of height h.
4. From text: problems R-3.5 and R-3.6 (p. 212).
5. Suppose we have a balanced binary search tree of some kind. The smallest
element stored in the tree is the leftmost descendant of the root, and the
largest is the rightmost descendant. Suppose we want to use the tree to find
efficiently the kth element in order. Can you think of a way to enrich the
information stored at every node, so that this operation can be performed in