# Maximum number of nodes that may not be full in an almost complete binary tree

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.

• Could you perhaps include your definitions of "almost complete binary tree" and "full" nodes so that there is no confusion about exactly what you are asking? Commented Mar 3, 2017 at 19:44
• Hi I just added my definitons. Thanks! Commented Mar 4, 2017 at 6:58

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.