Construct a Cartesian tree for the sequence 10 3 9 2 8 6 1 5 4.
Give 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?
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.
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.