Construct a Cartesian tree for the sequence 10 3 9 2 8 6 1 5 4.
Solution:
1
/ \
/ \
2 \
/ \ \
/ \ \
3 6 4
/ \ / /
10 9 8 5Give the sequence of depths in the Euler tour for the Cartesian tree from your answer to question 1. If we wished to find the minimum value in the subsequence 3 9 2 8 (from the second to fifth positions in the original sequence) which subsequence of the Euler tour depth sequence would this query translate to?
Solution: 1 2 3 4 3 4 3 2 3 4 3 2 1 2 3 2 1. If we number the positions of this solution sequence starting with 0, then the first position of node 3 in the Cartesian tree is at index 2, and the first position of node 8 is at index 9, so the subsequence of the depth sequence would be between those positions: 3 4 3 4 3 2 3 4. The minimum depth in this subsequence, 2, is the depth of node 2 in the Cartesian tree.
In an unrooted tree (a connected undirected graph with no cycles) the median $m(a,b,c)$ of three vertices $a$, $b$, and $c$ is the unique tree vertex that lies on each of the three shortest paths between the three pairs of nodes. Describe how to use lowest common ancestors to design a data structure that can represent an unrooted tree in $O(n)$ space and answer median queries in $O(1)$ time.
Solution: There are two possibilities. If $\mathrm{LCA}(a,b)=\mathrm{LCA}(b,c)=\mathrm{LCA}(a,c)$ (all three LCA's are the same) then that is also the median. Otherwise, two of the LCA's will be equal and one will be different than the other two. The median is the one that is different. (If the nodes are represented as index numbers then you could take their bitwise exclusive or but most programming languages won't let you do that with other kinds of data.)
Suppose that you wish to perform lowest common ancestor queries in rooted tree $T$, but that it has been stored in a data structure that can only answer level ancestor queries (given as arguments a vertex of $T$ and a depth $d$ of the ancestor to be found) in time $O(1)$ per query. Describe how to answer a lowest common ancestor query using $O(\log n)$ level ancestor queries.
Solution: Binary search for the largest $d$ such that both arguments to the LCA query have equal level ancestors at depth $d$.