2
$\begingroup$

Prove or disprove: the number of internal nodes in a complete binary tree of $K$ nodes is $\lfloor K/2 \rfloor$.

I tried using induction:

Base: 1 node $\rightarrow$ $0$ internal nodes

Assumption: let the number of internal nodes in a complete binary tree of $L$ nodes is $\lfloor L/2 \rfloor$

Inductive step: for $L+2$ we have one new internal node and $\lfloor L/2 \rfloor + 1 = \lfloor (L+2)/2 \rfloor $ and we're done.

But for $L+1$ ,as a complete graph can have one leaf,I get confused.

Anyone can help me?

$\endgroup$
2
$\begingroup$

HINT: When you add a new node, since this is a complete binary tree, there are two cases:

  1. Either the new node is the first of a new row,
  2. or the new node is added to the currently unfinished last one.

In the first case the number of internal nodes increments by one, as does the total number of nodes. The number of internal nodes was of the form $N - 1$, while the number of total nodes was $2N - 1$. Then in fact we have that $N = \left\lfloor\frac{2N}{2}\right\rfloor$.

In the second case...

$\endgroup$
  • $\begingroup$ in the second case no new internal nodes appear and the inductive step is the same as assumption. correct? $\endgroup$ – John Lennon Feb 3 '14 at 15:20
  • 1
    $\begingroup$ Almost. That's true when we are adding a leaf to a node that already has one: total number of nodes goes up by 1 while number of internal nodes stays the same. Then there's the case of adding a leaf to a node without children, which now becomes an internal node. $\endgroup$ – Jacopo Notarstefano Feb 3 '14 at 16:03

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.