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