Number of nodes of height $h$ in a heap or almost complete binary tree

Question

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

• Yuval Filmus: What is an "almost complete binary tree"?

Answer 1

Except for the next to last level all nodes are full, nothing to show. On the last level there are only leaves.

Only on the next to last level there can be non-full nodes, i.e. nodes with only one child. And there can be leaves. So your reformulation should be "X-1 nodes must be full or leaves."

Now it depends on the definition if the statement is true. If the last level must be filled from left to right, for example (this is the case if you implement the tree as an array), the next to last level looks like:

full full ... full (one possibly non-full) leaf leaf ...leaf

If another element is added, it must be a child of the non-full node and thus will make it full. If one element is removed, the non-full node will become a leaf.

As I said, the exact details depend on the exact definition of almost full binary tree. If the last level can be filled in an arbitrary manner, then the statement does not hold.