Practice Problem Set 8 Solutions
A sequence of parentheses defines a valid ordered tree if the parentheses are nested. This can be checked by maintaining an integer counter of the nesting level (initially zero), and looping over the sequence one character at a time, adding one to the counter for an open-parenthesis character and subtracting one for a close-parenthesis counter. The sequence is valid if the counter is zero at the end without ever having become negative. Describe a similar counter-based algorithm for checking whether a sequence of 1's and 0's defines a valid binary tree, using the binary tree representation described in the notes.
Solution: Set a counter for the number of nodes left to an initial value of 1, for the root. Loop over pairs of bits \(x\) and \(y\), for each pair adding \(x+y-1\) to the counter. The representation is valid if the counter is zero at the end without ever becoming zero earlier.
Suppose we have a rooted tree \(T\) in which each node is labeled by its depth, that is, its distance from the root. We wish to answer queries whose arguments are two nodes \(x\) and \(y\) and a number \(k\), and that test whether the distance from \(x\) to \(y\) is less than or equal to \(k\), returning True if it is and False otherwise.
Describe how to answer these queries using a single lowest common ancestor query in \(T\).
Solution:
return depth(x)+depth(y)-2*depth(LCA(x,y)) <= kDescribe how to answer these queries using two level ancestor queries in \(T\).
Solution (using level ancestor queries that ask for nodes with a given depth, not than for the number of steps higher):
d = (depth(x)+depth(y)-k+1) // 2
return LA(x,d) == LA(y,d)
Given two distinct vertices \(x\) and \(y\) in a tree, let \(s\) be the neighbor of \(x\) in the unique path from \(x\) to \(y\). That is, to follow a path from \(x\) to \(y\), the first step should be from \(x\) to \(s\). Describe how to use level-ancestor queries to compute \(s\) from \(x\) and \(y\) in constant time.
(The first step of your solution should be to determine whether \(s\) is the parent of \(x\) or a child of \(x\). In the case that \(s\) is is a child of \(x\), you need to compute which child. You can assume that the level-ancestor structure for the tree has already been constructed and that each node is labeled by its depth.)
Solution: If
x != LA(y,depth(x))then the path from \(x\) to \(y\) does not go down from \(x\) to a descendant of \(x\) and the first step is to the parent of \(x\). Otherwise, the first step is to the child of \(x\) given byLA(y,depth(x)-1).In any tree \(T\), a node \(x\) is an ancestor of another node \(y\) if and only if \(x\) occurs both before \(y\) in a preorder traversal of the tree, and after \(y\) in a postorder traversal. Therefore, it can be useful to store the nodes of a tree \(T\) in two list-ordering data structures, one for the preorder and one for the postorder. These two structures allow for constant time queries that answer the question: is \(x\) an ancestor of \(y\)? Suppose that we have a tree represented in this way, and we wish to insert a new node \(y\) as the last child of an existing node \(x\). What changes should we perform in the list-ordering data structures in order to make this change to the tree?
Solution: We need to insert \(y\) into the preorder after the last descendant of \(x\), or after \(x\) itself if it has no descendants, and into the postorder before \(x\).
Unfortunately it is not easy to find the last descendant, using only the preorder and postorder lists. Last year's solutions claimed that it could be done by checking whether the node \(z\) just before \(x\) in the postorder is a descendant of \(x\), and this does correctly find a descendant of \(x\) if one exists, but it will be the last child, not necessarily the last descendant. So the solutions were incorrect.
A solution that does work (but doesn't exactly answer the question as stated) is to maintain a single list-ordering data structure of the parentheses in a parenthesis representation of the tree, with each tree node maintaining pointers to its open and close parentheses in this list. Then the preorder is the ordering on the open parentheses, the postorder is the ordering on the close parentheses, and the insertion of \(y\) can be handled by inserting a parenthesis pair just before the close parenthesis of \(x\).