# internal nodes in a complete binary tree

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?

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