2
$\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$

migrated from stackoverflow.com Mar 3 '17 at 19:12

This question came from our site for professional and enthusiast programmers.

  • $\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 Mar 3 '17 at 19:44
  • $\begingroup$ Hi I just added my definitons. Thanks! $\endgroup$ – Blessen George Mar 4 '17 at 6:58
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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.