Prove through structural induction that a binary tree has an odd number of nodes

Question

A full binary tree is a binary tree where every node has either 0 or 2 children. Prove that every non-empty full binary tree has an odd number of nodes.

I dont know how to get started with this question. I know for a fact there are 2k+1 total nodes in a binary tree where k is the number of nodes with two children in an binary tree and 2j -1 total nodes in a binary tree where j is the number of nodes with no children. How do I use structural induction? Do I make two formulas comparing the two?

How about this:

if a binary tree has 0 nodes with children it has one node. if a node has two children the tree has at 3 nodes in it. Both the number of nodes are odd

Answer 1

Hint: Let $B$ be the set of all non-empty full binary trees. We can define $B$ recursively as follows:

• The graph consisting of a single node is in $B$.
• If $T_1, T_2 \in B$, then the graph $T$ consisting of a root node whose left and right subtrees are $T_1$ and $T_2$ is also in $B$.

It is clear that the graph consisting of a single node has an odd number of nodes. Now assume that $T_1$ and $T_2$ each have an odd number of nodes. Can you see why $T$ has an odd number of nodes? If so, then by structural induction, we're done!

Answer 2

My preferred definition of a non-empty, full binary tree is:

Definition 0. A pointed magma is an ordered triple $(X,\bullet,\star)$, such that:

• $X$ is a set
• $\bullet$ is an element of $X,$ and
• $\star$ is a function $X \times X \rightarrow X$.

Definition 1. Write $\mathbb{T}$ for the initial pointed magma, the elements of which are called non-empty full binary trees.

For example, here's an example of a non-empty full binary tree:

$$(\bullet \star \bullet) \star \bullet \in \mathbb{T}$$

This can be visualized as a tree, of course:

Okay. Let $\varphi : \mathbb{T} \rightarrow \mathbb{N}$ denote the node-counting function. Explicitly:

Definition 2. Define a function $\oplus : \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$ as follows: $$a\oplus b = a+b+1$$

Definition 3. Let $\varphi : (\mathbb{T},\bullet,\star) \rightarrow (\mathbb{N},1,\oplus)$ denote the unique such homomorphism of pointed magmas. We call $\varphi$ the node counting function.

For example, $$\varphi((\bullet \star \bullet) \star \bullet) = (1\oplus 1) \oplus 1 = 3 \oplus 1 = 5$$

So the above tree has $5$ nodes, as desired.

I claim that:

Claim. For all $x \in \mathbb{T}$, the natural number $\varphi(x)$ is odd.

This prove this, we need a way of performing induction on non-empty full binary trees. Here's a theorem that lets us do this:

Structural Induction for $\mathbb{T}$.

The pointed magma $(\mathbb{T},\bullet,\star)$ has no proper subalgebras.

More explicitly:

Structural Induction for $\mathbb{T}$. (Long form.)

Let $X$ denote a subset of $\mathbb{T}$.

If

1. $\bullet \in X$, and
2. for all $x,y \in X$, we have $x \star y \in X$,

then

$X = \mathbb{T}$.

Now we can prove our claim. Let $X$ denote the set of all $x \in \mathbb{T}$ such that $\varphi(x)$ is odd.

1. We know that $\bullet \in X$, since $\varphi(\bullet) = 1$ and $1$ is odd.

2. Assume $x,y \in X$. We will show that $x \star y \in X$. We know that $\varphi(x \star y) = \varphi(x) \oplus \varphi(y) = \varphi(x)+\varphi(y)+1.$ But the sum of three odd numbers is itself odd. So $\varphi(x \star y)$ is odd.

Hence by the structural induction theorem, we have $X=\mathbb{T}$. But recall that we defined $X$ as the set of all $x \in \mathbb{T}$ such that $\varphi(x)$ is odd. Thus $\mathbb{T}$ itself is the set of all $x \in \mathbb{T}$ such that $\varphi(x)$ is odd. In other words, $\varphi(x)$ is always odd, for all $x \in \mathbb{T}$. QED

---

A further comment.

It is worth noting that we can define the leaf-counting function in much the same way:

Definition 4. Let $\lambda : (\mathbb{T},\bullet,\star) \rightarrow (\mathbb{N},1,+)$ denote the unique such homomorphism of pointed magmas.

We call $\lambda$ the node counting function.

For instance, $$\lambda((\bullet \star \bullet) \star \bullet) = (1+1)+1 = 3,$$ so the aforementioned tree has $3$ leaves, as desired.

The cool thing about $\lambda$ is that it gives what is perhaps the most fundamental definition of the Catalan numbers; namely, writing $C_n$ for the $n$th Catalan number, we can define: $$C_n = |\lambda^{-1}(n+1)|$$

For example, $$C_2 = |\lambda^{-1}(3)| = |\{(\bullet \star \bullet) \star \bullet, \bullet \star (\bullet \star \bullet)\}| = 2$$