# Recursive Alegbraic Equation for binary trees? [duplicate]

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.

## marked as duplicate by Brian M. Scott, N. F. Taussig, Matt Samuel, colormegone, user147263 Feb 2 '15 at 1:28

• This is essentially the same question as this one, which has a couple of answers. If you combine those with MJD’s here, you should be in good shape. – Brian M. Scott Feb 1 '15 at 21:26

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.