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.
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\).
Describe how to answer these queries using two level ancestor queries in \(T\).
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.)
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 a 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?