Recursive Alegbraic Equation for binary trees?

Question

Consider the number $b_h$ of binary trees of height $h$, where height is being measured by the number of levels. An empty tree has height $0$, a single node binary tree has height $1$, and there are three trees of height $2$. Find a recursive algebraic equation for a sequence $b$, and prove for all natural numbers $h$ that $b_{h}$ is the number of binary trees of height $h$.

Assuming $b_{1} = 1$ binary Tree.

Then $b_{2} = 3$ binary Trees.

The difference is increasing by $+1$, $+2$, ..., $+(h-1)$.

How can we get the recursive algebraic equation for this? I'm really confused.

Answer 1

Let $T(h)$ be the number of trees of height $h$. When $h>1$, a tree of height $h$ has a left subtree and a right subtree. At least one of these subtrees must have height exactly $h-1$, and the other can have any height less than $h$.

So there are three ways to make a tree of height $h$:

1. The left subtree has height $h-1$ and the right has height less than $h-1$, or
2. The right subtree has height $h-1$ and the left has height less than $h-1$, or,
3. both subtrees have height exactly $h-1$.

You can write a term to count the number of trees of each of these three types. For example, how many trees have the shape of case 3? It must be $T(h-1)\cdot T(h-1)$, since there are $T(h-1)$ possible shapes for the left subtree and $T(h-1)$ possible shapes for the right subtree. $T(h)$ itself will be the sum of the three terms.

(You might want to hand-count the number of binary trees of height 3, to help yourself understand the problem better. To do this, try to systematically draw every possible binary tree of height 3, then count all the trees you drew.)