0

I'm trying to prove $i(T) = \frac{n(T)-1}{2}$ in a full binary tree where $i(T)$ is the number of the internal nodes (Nodes that don't have leaves) and $n(T)$ is the total number of nodes.

My base case is a full binary tree with 1 node as it would count as a leaf and satisfy the claim.

My inductive hypothesis is that a tree T with a node R and subtrees X and Y such that $i(X) = \frac{n(X)-1}{2}$ and $i(Y) = \frac{n(Y)-1}{2}$ are assumed.

I'm stuck on the actual inductive step on how to show this. How can I do this?

Q the Platypus
  • 4,626
Isk Kander
  • 13

1 Answers1

1

The number of leaves of $T$ is the sum of the number of leaves of $X$ and the number of leaves of $Y$. For the number of internal nodes you also need to add $1$ for the root.

Therefore we have

$$\begin{align} i(T) &= i(X) + i(Y) + 1 \\ &= \frac{n(X) - 1}{2} + \frac{n(Y) - 1}{2} + 1 \\ &= \frac{n(X) + n(Y) + 1 - 1}{2} \\ &= \frac{n(T) -1}{2} \enspace. \end{align} $$

Fabio Somenzi
  • 7,676