[Math] internal nodes in a complete binary tree

graph theory

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?

Best Answer

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...

Related Question