3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – user642796
    Commented Mar 3, 2017 at 19:44
  • $\begingroup$ Hi I just added my definitons. Thanks! $\endgroup$ Commented Mar 4, 2017 at 6:58

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .