While writing a code about Huffman coding (it doesn't matter what it is), I came with an idea that I could check whether the tree would be flat* without actually constructing it. For that quick check (which I won't specify here) to work, it would suffice that one little lemma is true and that is what I couldn't prove.
The hypothesis:
Every rooted tree which satisfies:
- it is completely binary,
- the number of leaves in it is a power of 2 and
- if it has a leaf at depth $d$, then it has less than $2^{k-1}$ leaves at depth $d+k$, for all $k\ge2$,
is necessarily flat.
My thoughts:
It is hard to test because of the condition 2: there are just a few completely binary trees with 2 and 4 leaves, but many with 8. However, I didn't find any counterexample to this hypothesis. I tried to prove it clasically case by case together with simple logic but nothing… I also tried formulating the conditions in terms of series where $i$-th coefficient is the number of leaves at depth $i$, but it didn't see much glory either.
The definitions:
a tree is a finite non-empty acyclic graph,
a rooted tree is a tree with one distinguished node called the root,
the depth of a node $x$ in a rooted tree is the number of edges in the shortest path from $x$ to the root,
a child of a node $x$ in a rooted tree is a neighbour of $x$ which is not on the shortest path from $x$ to the root,
a leaf of a rooted tree is its node with no children,
a completely binary tree is a rooted tree where every node has exactly 0 or 2 children,
a flat tree is a rooted tree whose all leaves have the same depth.
Best Answer
As @FabiusWiesner pointed out, we can assign a weight equal to $1 / 2^j$ to each node at depth $j$, let $n_j$ denote the number of leaves at depth $j$, and let $m$ be the maximum depth such that $n_m > 0$.
Then condition 1 "completely binary" can be rephrased as $\sum_{j=0}^m n_j / 2^j = 1$ (consider root with weight $1$ and each node splits its weight into halves to its two children).
The condition 2 can be rephrased as $\sum_{j = 0}^m n_j$ is a power of 2.
Now, let $d$ be the minimum depth such that $n_{d} > 0$.
Assume $m > d$. First, we can see that it is impossible that $m = d + 1$. To see this, $n_d + n_{d+1}$ needs to be a power of two, while $n_d + \frac{1}{2} n_{d+1} = 2^d$. Since $n_{d+1} < 2^{d + 1}$, $2^d < n_d + n_{d+1} < 2^d + 2^d = 2^{d+1}$. So, if $m \neq d$, then we must have $m \geq d + 2$.
Fact: $n_m$ is even and thus is at least $2$.
We claim that $n_{m-1} \geq 2$. To see this, assume the opposite, i.e., $n_{m-1} \leq 1$, and let $s \geq 2$ be the minimum at-least-2 positive integer such that $n_{m - s} > 0$. Then, since $\sum_{j = 0}^{m - s} n_j / 2^j < 1$ and thus $\sum_{j = 0}^{m - s} n_j / 2^j \leq 1 - 2^{s - m}$, it is easy to see that we need $n_m 2^{-s} + n_{m-1} 2^{-s + 1} \geq 1$, but by condition 3 and $n_{m-1} \leq 1$, we have $n_m 2^{-s} + n_{m-1} 2^{-s + 1} < 2^{s - 1} 2^{-s} + 2^{-s + 1} \leq 1/2 + 1/2 = 1$.
Then by condition 3, $n_{m-2} = n_{m - 3} = 0$.
Now, let $t > 2$ be the minimum at-least-2 positive integer such that $n_{m - 1 - t} > 0$ (there must be one since $m \geq d + 2$). We have $\sum_{j = 0}^{m - 1 - t} n_j / 2^j < 1$ and thus it is easy to see that $\sum_{j = 0}^{m - 1 - t} n_j / 2^j \leq 1 - 2^{t + 1 - m}$, which requires that $n_{m - 1} 2^{1 - m} + n_m 2^{- m} \geq 2^{t + 1 - m}$. However, by condition 3, we have $n_{m - 1} < 2^{t - 1}$ and $n_m < 2^t$, which gives $n_{m - 1} 2^{1 - m} + n_m 2^{- m} < 2^{t - 1} 2^{1 - m} + 2^t 2^{- m} = 2^{t - 1 + m}$, completing the proof by contradiction.
Note: Seemingly the conditions are overly strong. Maybe we can prove the same thing with weaker conditions.