The emphasis in this set of questions is on the construction of simple yet efficient tree algorithms.
| Question 1 | Complete binary trees. A complete binary tree is implemented with the help of left and right pointers, and not as an array as is common practice. Nodes in a complete binary tree have a standard numbering system, where the root has number 1, its children numbers 2 and 3 and so forth. The operation locate (n,T) locates the node with number n in a tree T, where T may be considered as a pointer to the root. This must be done in O(log n) time using only O(log n) extra space. The operations log and exp are not available, but +, -, mod and idiv (integer division) are. Give an algorithm. |
| Question 2 | Recursions. A binary tree is given in which each node is an integer between 1 and n, and the structure is contained in the arrays left[.] and right[.] (left[x] is the left child of node x). Give recursive pseudocode for determining all entries of an array h[.], where h[x] is the height of the subtree rooted at x. How long does your algorithm take? |
| Question 3 | Recursions. Let us continue question 2. Give a simple recursive algorithm for determining the length of the longest path in the binary tree. Prove that your algorithm takes time O(n). |
| Question 4 | Binary search trees. In a binary search tree stored in the usual fashion with fields left[.] and right[.] for the children, and a field key[.] for the key of a node, we would like to efficiently implement the function lca (x,y,t), where t is a tree root, and x,y are key values of some nodes. The function is to return the node that is the least common ancestor of the nodes with keys x and y (that is, of all the common ancestors, take the one that is furthest from the root). |
| Question 5 | Tree algorithms. We are given an ordered sequence x_1 < x_2 < ... < x_n in array format. These elements have to be put into a binary search tree of minimal height, stored in the standard left[.], right[.] pointer format. Explain how you can do this in time O(n). |
| Question 6 | A proof. Prove that if x is a node in a binary search tree stored with left, right and parent pointers, then the sequence of k consecutive operations x=successor(x) takes time bounded by a constant times (h+k), where h is the height of the tree, and "successor" is implemented as described in the lectures. |
Copyright © 1999 Luc Devroye. Email: luc@cs.mcgill.ca.