Full binary tree theorem proof validity?

Question

I'm reviewing some of the theorems that make up the Full binary tree theorem and want to make sure my proof for how the number of internal nodes $I$ is related to the number of total nodes $N$ is correct.

I realize you could relate the number of internal nodes to the number of leaves and them simply add, and go from there but I'm trying not to use that proof in this example.

I'm using induction and I believe my proof valid but something about it seems so simple (and a bit wordy) I'm not sure if I'm missing something. Also if there are any other proofs someone would like to dish out that would be great. I realize you could do this purely with numbers and less "english" if trying to prove this on a perfect binary tree (much tighter restrictions on the tree), however the most concise way I can think of proving this for a full binary tree is rather wordy, and below.

The total number of nodes $N$ in a tree with $I$ internal nodes is $2I + 1$

Base case

A tree with $0$ internal nodes $I$ has $2(0) + 1 = 1$ total nodes.

Assumption

Let's assume that any full binary tree with $I$ internal nodes has $2I+1$ total nodes $N$.

Inductive step

Given a tree $T$ with $I+1$ internal nodes, take one of it's internal nodes whose children are both leaves and remove it's children. $T$ now has one less internal node or $I$ internal nodes meaning it has $2I+1$ total nodes. If we add the children back to our selected node, the number of internal nodes increases by $1 \text{ from } I \Rightarrow I+1$ and our total number of nodes $N$ increases by $2 \text{ from } 2I+1 \Rightarrow 2I+3$ which is the same as $2(I+1) + 1 \quad \blacksquare$.

Answer 1

You went slightly astray with the last sentence: you lost track of the number of internal nodes. If we add the children back in, the number of internal nodes increases by $1$ from $I$ to $I+1$, not from $I+1$ to $I+2$. You also need to show that there actually is an internal node whose children are both leaves. If you’ve already defined the height (or depth, depending on your terminology) of a node, you can pick a leaf $v$ whose height is maximal: its sister must also be a leaf. You can also add a little connective tissue to the induction step, something like this:

Suppose that the result is true for all full binary trees with $I$ internal nodes, and let $T$ be a full binary tree with $I+1$ internal nodes and $N$ nodes altogether. $T$ has at least one internal node, so it must have a leaf; let $v$ be a leaf of maximal height, so that its sister is necessarily also a leaf. Remove $v$ and its sister, and let $T'$ be the resulting tree; the parent of $v$, which was an internal node of $T$, is a leaf of $T'$, and the status of the other nodes of $T'$ is unchanged, so $T'$ has $I$ internal nodes. It is also a full binary tree, so by the induction hypothesis $T'$ has $2I+1$ nodes altogether. Clearly $N=(2I+1)+2=2(I+1)+1$, as desired.

Answer 2

To carry out the inductive step, you need an internal node with two leaves. You might have to prove that such a node exists for $I\geq1$ in a full binary tree. You can avoid that by choosing any internal node except the root and removing the full subtree rooted at it, thereby adding a leaf node to the original tree in its place.

This, however, needs a full tree with a non-root internal node in the inductive step, that is, $I\geq2$, so consideration of $I=1$ must be added as base case.

Answer 3

Let $N$ be the total nodes in tree $T$, of which $I$ nodes are internal. Since, the root vertex of a binary tree is of degree $2$, $(N-I)$ leaves are of degree $1$ and rest $(I-1)$ vertices of degree $3$, thus by Handshaking theorem, one gets

$\sum_{r=0}^{n}deg(v_r)=2(no. of edges)$

$\implies 2+(N-I)+3(I-1)=2(N-1)$

$\implies N=2I+1$