Optimizing (sort of) a binary tree shape

12 Views Asked by At

Let's define with respect to a binary tree $T$ (I'm sure that some notions are known, but I don't know the established names):

  • The "total height" $h(T)$ is the sum of all leaf heights of $T$.

  • An "full" $T$ has only even numbers of children for any node ($0$ or $2$).

  • A (left) "comb" is a special $T$ where all left children are leaves (and has the minimum number of nodes for a full $T$).

Example: The Wiki binary tree has $m=9$, is not full (exactly the nodes containing a $9$ are odd) and is obviously no comb. $h(T)=3+4+4+4=15$. It is not optimal: A comb would have, with maximum height $H=(m+1)/2$, $h=(H+1)(H+2)/2-2=19$.

Let $T$ be a binary tree with $m$ nodes. Which shape of $T$ gives a maximum $h$? I suspect it's a comb, which is also full. Assuming I'm wrong, which full $T$ gives a maximum $h$?