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.

    Solution:

    Cartesian tree
  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.

    Solution: (2,0) (4,1) (18,2) (21,3) (18,2) (4,1) (6,2) (19,3) (25,4) (19,3) (20,4) (22,5) (24,6)* (22,5) (20,4) (19,3) (6,2) (4,1) (2,0) (10,1) (13,2)* (17,3) (13,2) (10,1) (2,0)
  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.

    Solution: One such solution is "-+-+". If this sequence occurred, the first "-" would correspond to following an edge from a child in the tree to its second, the next "+-" would visit and return from a second child of the same parent, and the final "+" would visit a third child of the same parent. But in the Cartesian tree, each parent has at most two children, so this sequence is not possible.
  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.

    Solution: Assume $x\ne y$ (otherwise there is no first step). For each child $z$ of $x$, if the lowest common ancestor of $z$ and $y$ equals $z$, then the first step from $x$ to $y$ passes through $z$. If there is no child $z$ for which this is true, then the first step of the path passes through the parent of $x$.