CS251- Winter 1999- Practice questions

Answers to first set of practice questions--CS251--Winter 1999

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.
Answer	Consider the binary expansions of the node numbers, and drop the leading 1. For example, node 14 has binary expansion 1110. Without the leading 1, we obtain 110. Verify that 110 describes the path to be taken from the root to node 14, where 1 denotes "take a right turn" and 0 says "take a left turn", very much as in a trie. It is therefore trivial to right an algorithm that finds any node in O(log n) time, as complete binary trees with n nodes have height <= log_2 n.
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?
Answer	Let h[.] be an external array, initialized to zero. For the height of a node x, we have the recursion h[x] = max (left[x], right[x]) + 1 if x has at least one child, and h[x] = 0 otherwise. Thus, we can compute h[x] AFTER having computed h[left[x]] and h[right[x]]. Our recursive program will be called compute-h: compute-h (x: node): integer; (returns h[x]) if x = nil, then return 0 if x != nil, and x has no children, then h[x]=0; return 0 otherwise: LH = compute-h (left[x]) RH = compute-h (right[x]) h[x]=1 + max(LH,RH); return h[x] This algorithm visits every node once when called with compute-h (rootnode), and takes O(1) work per call. Hence it takes O(n) time in all.
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).
Answer	First compute the fields h[x] as in the previous question. This takes time O(n). For the longest path, there is a simple recursion: longestpath(x: node); (returns length of longest path in subtree rooted at x) if x=nil then return 0 if left[x]=nil then leftheight=0 else leftheight=h[left[x]]+1; if right[x]=nil then rightheight=0 else rightheight=h[right[x]]+1; paththroughroot=leftheight+rightheight; return max (paththroughroot, longestpath(left[x]), longestpath(right[x]) ); The algorithm above makes use of the fact that the longest path either goes through the root (in which case it is the sum of left heights and right heights as indicated in the code), or it does not (in which case, it is the maximum of the longest path lengths of both subtrees). The algorithm visits each node x once and takes O(1) time per call. Hence the toal time is 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).
Answer	Assume without loss of generality that key[x] < key[y]. If we start searching for x and y at the root, and stop when we first encounter z with key [x] <= key [z] <= key [y], then that z must be the least common ancestor (which may be x or y itself). lca (x,y,t): returns a node; while (t != nil) do: if key[x] <= key [t] <= key [y] then return t if key[y] < key[t] then t <- left[t] if key[x] > key[t] then t <- right[t]
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).
Answer	Again, we use a recursion. Of course, the middle element should become the root. Therefore, our recursive function will return the root of the subtree: treemake (i,j) returns the root of the subtree holding x_i ,..., x_j, and fixes the pointers for that root. treemake (i,j): integer; root = floor of (i+j)/2 if i <= root-1 then left[root]=treemake(i,root-1) else left[root]=NIL if root+1 <= j then right[root]=treemake(root+1,j) else right[root]=NIL return root We call treemake (1,n), and note that treemake can at most be called n times. Each execution of treemake takes O(1) time, and thus the total time is 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.
Answer	Let a be the starting node and let b be the last node (so that the rank of b is k more than the rank of a). Note that every node visited by going from a to b via the "successor" operation is either a node whose key value is between the key values of a and b, or a node that is an ancestor of either a or b. The total number of nodes visited can not exceed k + 2h. As each visit contributes one time unit to the total time, the total time is not more than k+2h <= 2(k+h).