Best case “skew height” of an arbitrary tree

Question

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).

Answer 1

For a binary tree, let $H(T)=\min_AH_A(T)$, where $A$ ranges over all favored-child assignments of $T$. Call $H(T)$ the skew height of $T$.

Here is a simple observation. The skew height of a perfect binary tree of (ordinary) height $n$ is $n$, too.

For a binary tree $T$, an edge is called a passing edge if one of the endpoints has exactly one child. We call a binary tree $M$ a b-minor of $T$ if $M$ can be obtained by removing a subtree or contracting a passing edge repeatedly.

For a binary tree $T$, what is its skew height? Here is a visual characterization.

The skew height of $T$ is the maximum (ordinary) height of all perfect binary trees that are also b-minors of $T$. Intuitively speaking, a binary tree is of skew height $s$ $\iff$ it "contains" a perfect binary tree of ordinary height $s$.

Proof. Since both removing a subtree and contracting a passing edge do not increase the skew height, $$H(T)\ge \max_{M\text{ is a b-minor of T}}\mathsf{height}(M),$$ where $\mathsf{height}(\cdot)$ is the (ordinary) height of a tree. On the other hand, by induction on the number of nodes of $T$, we can show that a binary tree of skew height $s$ must contain a b-minor that is a perfect binary tree of ordinary height $s$. $\quad\checkmark$.

---

Recall that $n$ is the number of nodes in $T$. We have, $$H(T) \le \lceil \log_2(n+1)\rceil - 1.$$ Proof. Induction on $n$. The base case, $n = 1$ is easy to verify.

Suppose it is true if the number of nodes in $T$ is smaller than $n$. Consider a binary tree $T$ of $n$ nodes with root node $r$.

• If $r$ has only one child, say, $a$, then $$H(T)=H(\text{the subtree rooted at } a)\le \lceil \log_2((n-1)+1)\rceil - 1\le \lceil \log_2(n+1)\rceil - 1.$$
• If $r$ has two children, say, $a$ and $b$. Since the number of nodes in the subtree rooted at $a$ and the subtree rooted at $b$ is $n-1$, one of the subtrees has at most $\lfloor (n-1)/2\rfloor$ nodes. WLOG, suppose it is the subtree rooted at $b$. Then $$H(T)=\max(H(\text{the subtree rooted at }a ) + 1, H(\text{the subtree rooted at } b)) \\ \le \max(\lceil \log_2(\lfloor(n-1)/2\rfloor+1)\rceil,\lceil \log_2((n-2)+1)\rceil -1) $$ Since $$ \lceil \log_2(\lfloor(n-1)/2\rfloor+1)\rceil=\lceil \log_2(\lfloor(n+1)/2\rfloor)\rceil=\lceil \log_2(n+1)\rceil-1,$$ we have $H(T)\le \lceil \log_2(n+1)\rceil-1.$ $\quad\checkmark$

---

Recall that $f(n)=\max_{T\text{ is a binary tree and }|T|=n}H(T)$. The above section has proved $f(n)\le \lceil\log_2(n+1)\rceil-1$.

On the other hand, the skew weight of the perfect binary tree with $2^m-1$ node is $m-1$. Hence, $$f(n)=\lceil\log_2(n+1)\rceil-1.$$