# 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? Mar 3 '17 at 19:44
• Hi I just added my definitons. Thanks! Mar 4 '17 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.