I'm working through the full binary tree proofs for a blog post I'm writing and I want to make sure I'm not missing anything. This particular proof focuses on relating the number of total nodes $N$ to the number of leaves $L$. I find it easier to induct on $L$ and the following is my proof:
The total number of nodes $N$ in a full binary tree with $L$ leaves is $N = 2L – 1$
We can prove $N = 2L – 1$ by induction.
Base case
A tree with $1$ leaf has $1$ node altogether.
A tree with $2$ leaves has $3$ nodes altogether.
Base case proves the theorem for $L = 1$ & $L = 2$.
Inductive hypothesis
Let's assume that any full binary tree with $L$ leaves has $N = 2L – 1$ total nodes.
Inductive step
Prove that all any full binary tree with $L+1$ leaves has $N = 2(L+1) – 1$ total nodes.
Let $T$ be a full binary tree with $L+1$ leaves. Select a leaf $v$ at maximal depth such
that $v$'s sibling is also a leaf at maximal depth. Remove both $v$ and $v$'s sibling and let
$T'$ be the resulting tree. $T'$ is a full binary tree with $L$ leaves which by our inductive
hypothesis must have $2L – 1$ total nodes $N$. Note $v$'s parent is now a leaf in tree $T'$.
Add $v$ and $v$'s sibling back to their parent and notice the parent becomes an internal node
thus the tree loses one leaf, but gains another two (that we added). The number of leaves increased by a total
of $1 \text{ from } L \Rightarrow L+1$ while the number of nodes increased by two $2L – 1 + 2 = 2L + 1$.
This clearly equals $2(L+1) – 1$ thus proving by induction that the number of total nodes $N$ in any full
binary tree with $L$ leaves is $2L – 1 \quad \blacksquare$.
Is this proof valid or am I leaving something out?
I'm curious, if I were to induct on $N$ instead of $L$, I would obviously have to prove that a tree with $N+2$ nodes has $\frac{(N+1)+2}{2}$ leaves since a tree with $N+1$ nodes cannot be a full binary tree if a tree with $N$ nodes is a full binary tree. Would I have to do anything special to explain my stepping from $N \Rightarrow N+1$. The reason a tree with $N+2$ nodes is a full binary tree if a tree with $N$ nodes is a full binary tree is simply because of the recursive definition of a full binary tree but I don't know how else to articulate that (or if I need to). Is this what structural induction is?
Edit: Proof based on splitting
Base case
A tree with $1$ leaf has $1$ node altogether.
A tree with $2$ leaves has $3$ nodes altogether.
Base case proves the theorem for $L = 1$ & $L = 2$.
Strong Inductive hypothesis
Let's assume that any full binary tree with $L$ leaves has $N = 2L – 1$ total nodes for all $0 \leq L \leq K$.
Inductive step
Let $T$ be a full binary tree with $K+1$ leaves. Seeing how $T$ is a full binary tree, its subtrees $T_{left}$ and $T_{right}$ must have at least $1$ leaf each. This means $T_{left}$ and $T_{right}$ have a number of leaves $< K+1$. Call this number $L_{left}$ and $L_{right}$ respectively. By our strong IH, they must have $2(L_{left}) – 1$ and $2(L_{right}) – 1$ total nodes respectively. $T$ therefore has a number of nodes equal to the sum of the number of nodes in each subtree plus its root which appears not in either subtree. Since the only node not appearing in either of $T$'s subtree is an internal node and not a leaf, the number of leaves in $T = L_{left} + L_{right}$.
$$2(L_{left}) – 1 + 2(L_{right}) – 1 + 1 = 2(L_{left} + L_{right}) – 2 + 1 = 2(K+1) – 1 = 2(L+1) – 1$$
Thus proving by induction that all full binary trees with $L$ leaves have $N = 2L – 1$ total nodes for all $L \quad \blacksquare$.
Best Answer
Your proof looks good. It's not the only way of proving this (as usual) - I would perhaps find the option to split on the root node a more natural approach for a binary tree.
I don't think induction on $N$ would be easy to frame or justify. Certainly when you're trying to prove something in which the given fact is about $L$ and the result is about $N$ you would have to do some work to turn it round.