Assuming the following definitions:
Full Node: A full node is the root of a tree in which every non-leaf node has two children and all the leaves are at the same level/depth.
Almost Complete Tree: A tree in which all levels are completely filled except possibly the last and all leaves are as far left as possible.
I came up with the following statement:
- "If there are $x$ nodes of height $h$ in an almost complete binary tree, there can be at most $1$ node of height $h$ that is not full."
That is to say $x-1$ must be full and the last node of height $h$ may or may not be full.
Intuitively it seems right, but I can't seem to prove it. Could someone help me prove it? If the statement is false, please let me know why.
Proof idea: Assume toward a contradiction that there are two nodes $v_1$ and $v_2$ of height $h$ that are not full. Without loss of generality, assume $v_1$ is left of $v_2$ (this can be defined because they have the same height). Since the tree rooted by $v_1$ is not full, there is a "missing leave" in this tree. Since all levels except the last one are full, the trees rooted by $v_1$ and $v_2$ both contain a leave on the last level of the overall tree. Moreover, all leaves under $v_2$ are right of all leaves under $v_1$. In particular, there is a leave under $v_2$ on the last level that is right of the "missing leave". Hence, not all leaves are as far left as possible, contradicting the tree being almost complete.