I have to provide a structural proof for this: show that $l(T)$, the number of leaves of a full binary tree $T$, is 1 more than $i(T )$, the number of internal vertices of $T$.

I have the following, and I'm wondering if I'm doing this correctly. I have no idea what the inductive hypothesis is here... Thanks in advance!

The set of all full binary trees $B$ can be defined recursively as:

$T_0$ is in $B$ such that $T_0$ has $i(T_0) = 1$ number of internal vertices and $l(T_0) = 2$ number of leaves.

For any tree $T_n$ in $B$, $T_{n+1}$ is in $B$ such that $T_{n+1}$ has $i(T_{n+1}) = i(T_n) + 1$ number of internal vertices, and $l(T_{n+1}) = l({T_n}) + 1 $ number of leaves.

Structural Inductive Proof:

Base Step:

Tree $T_0$ has 1 internal vertex and 2 leaves. so the number of leaves is 1 more than the number of internal vertices.

Inductive Step:

Since, each tree in $B$ is generated from the base case by adding 1 to the number of leaves and 1 to the number of vertices, and since the base tree in $B$ has 1 more leaf than internal vertex, every full binary tree has 1 more leaf than internal vertex.


As Andreas Blass said, you need to start with an actual recursive definition of full binary tree. What’s the smallest, simplest full binary tree? It’s the tree with a single vertex and no edges; take that as your starting point. If you have a full binary tree, how do you build the next larger one? You attach a pair of edges and vertices to each leaf; that’s your construction step. Put those together (and add the usual limiting statement), and you have your definition:

  1. The tree with one vertex and no edges is a full binary tree.
  2. Suppose that $T$ is a full binary tree with leaves $v_1,\dots,v_n$. Let $u_1,\dots,u_n$ and $w_1,\dots,w_n$ be $2n$ new vertices. Add these vertices to $T$, and for $k=1,\dots,n$ add edges from $v_k$ to $u_k$ and $w_k$; the resulting graph is a full binary tree.
  3. A graph is a full binary tree if and only if it is required by clauses (1) and (2) to be one.

Now see if you can prove your theorem by structural induction from this definition. Certainly the induction gets off the ground easily enough: The one-vertex graph has one leaf and no internal vertices, and $1=0+1$.


First of all, your recursive definition of the set $B$ of full binary trees doesn't seem to define the trees at all. In particular, it doesn't tell us what $T_{n+1}$ is (in terms of $T_n$); rather it only tells us how many internal vertices and how many leaves it should have.

Second, still referring to this "definition" of $T_{n+1}$, the counts of vertices seem to be wrong. Draw pictures of the trees $T_0$ and $T_1$, and notice that the number of internal nodes and the number of leaves have both increased by more than 1. (Since your "definition" doesn't actually define the trees, I'm assuming that "full binary tree" $T_n$ means a tree with a root at level 0, where every node at level $\leq n$ has exactly two "children", and each node at level $n+1$ is a leaf. I'd be inclined to call that $T_{n+1}$, but your description of $T_0$ indicates that your numbering differs by 1 from my preference.)

  • $\begingroup$ If I add that $T_{n+1}$ must also be a binary tree, does that help?I'm not sure what the appropriate vocabulary is. But, would it be more clear if I said that $T_{n+1}$ adds (or appends?) two leaf nodes to a leaf node in $T$? Thanks! $\endgroup$ – papercuts Feb 14 '13 at 21:10

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.