This question already has an answer here:

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 question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ 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. $\endgroup$ – 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.

(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.)


Not the answer you're looking for? Browse other questions tagged or ask your own question.