Given an arbitrary binary tree on $ n$ nodes, choose an assignment $ A$ from each parent to one of its children (the "favored child" as it were). We define the skew height of the tree as $ H_A(\mathsf{nil})=0$ and $ H_A(\mathsf{node}\;a\;b)=\max(H_A(a), H_A(b)+1)$ if $ A(\mathsf{node}\;a\;b)=a$ is the favored child and symmetrically $ \max(H_A(a)+1, H_A(b))$ if $ b$ is favored.

The question is: For a fixed tree $ T$ , what is the minimum skew height over all assignments? I would like to get an asymptotic bound on $ f(n)=\max_{|T|=n}\min_AH_A(T)$ .

Other variations on this problem I am interested in are when the trees are not binary (but there is still one favored child and all others add one to the height), and when there is sharing (i.e. it is a dag), which doesn’t affect the height computation but allows for much wider "trees" while staying under the $ n$ node bound.

The obvious bounds are $ f(n)=\Omega(\log n)$ and $ f(n)=O(n)$ . My guess is that $ f(n)=\Theta(\log n)$ for binary trees, and $ f(n)=\Theta(\sqrt n)$ for dags (with some kind of grid graph as counterexample).