CompSci 261, Spring 2017, Homework 7

1. Draw a Cartesian tree for the sequence 18, 21, 4, 25, 19, 20, 22, 24, 6, 11, 2, 10, 13, 17. In the tree, indicate the pair of nodes such that a lowest common ancestor query for this pair would correspond to a range minimum query for the subsequence from 24 to 13.

2. List the nodes in the tree you drew for the previous problem, in the order given by an Euler tour of the tree. Each node should be listed as a pair (depth,value); some nodes should appear more than once in your list. Indicate the pair of positions in the list that would correspond to the LCA query from your previous answer.

3. In the sequence of depths of nodes in a Cartesian tree, the first depth is zero and each depth differs from the previous one by either $+1$ or $-1$, so if the the whole sequence of depths has length $n$, it can be encoded by a sequence of $n-1$ symbols, each of which is either "+" or "-", indicating the change from one depth to the next. Give a subsequence of "+" and "-" symbols that cannot occur (consecutively) within this sequence, and explain why it cannot occur.

4. Suppose that $T$ is a rooted binary tree, in which each node has pointers or references to its left and right children (if they exist) and to its parent (unless it is the root). Suppose also that we have already constructed a lowest common ancestor query data structure for $T$. We are also given two nodes in the tree, $x$ and $y$, and we wish to find the path in the tree that connects $x$ to $y$. Explain how to use a constant number of lowest common ancestor queries to find the first step (the neighbor of $x$) in this path.