2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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:

enter image description here

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

$\endgroup$
0
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Is it because of the base case? Since a single node is in T there is an odd number of nodes. If the tree had an even number of nodes it wouldn't be in the set because of the base case? How do I word it as a formal proof $\endgroup$ – Manny Pwety Oct 8 '14 at 5:35
  • $\begingroup$ Ignore the base case. Think about how $T$ is defined in terms of $T_1$ and $T_2$. Think about the parity of the number of nodes in $T$, given that each subtree has an odd number of nodes. $\endgroup$ – Adriano Oct 8 '14 at 7:26

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.