1
$\begingroup$

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

$\endgroup$
11
  • $\begingroup$ "if $A(\mathsf{node}\;a\;b)=a$ is the favored child". What does "$\mathsf{node}\;a\;b$" mean? Does it mean the parent node of node $a$ and node $b$? $\endgroup$ – John L. Jun 24 '20 at 3:46
  • $\begingroup$ Oh, I see. It looks like $H$ is defined on the sets of childrens. Then what does it mean by $H_A(T)$? $\endgroup$ – John L. Jun 24 '20 at 3:57
  • $\begingroup$ On the other hand, it is obvious what you are trying to define. (The more I check your definition, the more confused I am. However, the phrases "favored child" and "skew height" describes the whole situation pretty much.) Here is my description. For each node $p$, select a favored child $A(p)$, which is nil if $p$ has no child. $B(p)$ will be the other child of $p$ or nil if there is no other child. The skew height of each node $H_A(p)=\max(H_A(A(p), B(p)+1)$. $H_A(\mathsf{nil})=0$. The skew height of the tree is the skew height of its root node. $\endgroup$ – John L. Jun 24 '20 at 4:07
  • $\begingroup$ The formula should been $H_A(p)=\max(H_A(A(p)), H_A(B(p))+1.$ $\endgroup$ – John L. Jun 24 '20 at 4:12
  • 1
    $\begingroup$ A way to picture the definition is that we are drawing the tree such that one child goes down and the other child goes to the left, and the question is how to lay out the tree such that it has the minimum vertical extent (and what tree is the worst case for such optimization). (In fact it's not just a visual aid, this problem originally came out of a pretty printing optimization problem for laying out trees using indentation.) $\endgroup$ – Mario Carneiro Jun 24 '20 at 5:13
1
$\begingroup$

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.

a perfect binary tree of height 2

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

$\endgroup$
1
  • $\begingroup$ For dags, $f(n)=\lfloor (n-1)/2\rfloor$. First we prove that $f(n)\le\lfloor (n-1)/2\rfloor$ by induction on $n$. Second, consider graph $P$ with nodes $v_1, \cdots, v_n$ and directed edges $(v_i, v_j)$ for all $i<j$. Verify that $H(P)=\lfloor (n-1)/2\rfloor$. $\endgroup$ – John L. Jun 26 '20 at 21:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.