2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Yeah the splitting would probably be more natural. But if you were given $L$ as a fact and the result about $N$, couldn't you just flip it, and say $N = 2L - 1$ is only true if $L = \frac{N+1}{2}$ is true, then induct on N and prove the second equation? Or is this not valid... $\endgroup$ – Dominic Farolino Jul 3 '16 at 18:55
  • $\begingroup$ Possibly, but given that we have the fairly natural approach you used (and the alternative of a tree split) I doubt that it would "feel" right to try to reverse into the proof like that. $\endgroup$ – Joffan Jul 3 '16 at 19:20
  • $\begingroup$ Could you take a look at the second proof I added based on splitting? $\endgroup$ – Dominic Farolino Jul 3 '16 at 21:17
  • $\begingroup$ Looks OK, except $K$ suddenly became $L$ on the last line :-) and you left off the magic words (not uncommon in inductive proofs) - "This shows that induction holds and therefore [[general result]]" $\endgroup$ – Joffan Jul 3 '16 at 21:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.