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
- $\bullet \in X$, and
- 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.
We know that $\bullet \in X$, since $\varphi(\bullet) = 1$ and $1$ is odd.
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$$
Outline of proof
Prove it for $1$ leaf node (which is just the graph with one node.)
Then assume it is true for complete binary trees with $n\geq 1$ leaf nodes.
Given a complete binary tree with $n+1$ leaf nodes, show that at least two of the leaves must have a common parent.
Remove those two leaf nodes, and their parent becomes a leaf node, so you are left with a complete binary tree with $n$ leaf nodes. (Proof of that is required.)
Apply the induction hypothesis. To the graph with $n$ leaf nodes. Now note that the original graph had one additional internal node, and one additional leaf node.
Best Answer
Proof by induction on the height h of a binary tree.
Base case: h=1
There is only one such tree with one leaf node and no full node. Hence the statement holds for base case.
Inductive step: h=k+1
case 1: root is not a full node.
WLOG we assume it does not have a right child. In this case the number of full nodes and the the number of leaf nodes is equal to the tree which is rooted at at's left child. Since the height of that left subtree is k, by induction the difference should be 1.
case 2: root is full node.
total number of leaf nodes = leaf node in tree rooted at it's left and right.
total number of full nodes = 1 (the root itself) + the number of full nodes to its left and right.
Thus the difference remains 1.
Proved.