How many unlabeled binary trees of height 2

737 Views Asked by At

Binary trees of height 2 to me means the tree either has 3 nodes or 2 nodes. So I thought it would be $C_3 +C_2 = 7$ where $C_n$ is the nth Catalan number. But I am being told that I am under-counting but don't understand why.

1

There are 1 best solutions below

0
On

A binary tree of height $2$ must have at least $3$ nodes: the root, at least one at height $1$, and at least one at height $2$. There are $4$ binary trees of height $2$ that have this minimum of $3$ nodes:

         *             *              *             *
        /             /                \             \
       *             *                  *             *
      /               \                /               \
     *                 *              *                 *

There are two more that have just one node at height $1$:

              *                    *
             /                      \
            *                        *
           / \                      / \
          *   *                    *   *

All of the rest have $2$ nodes at height $1$ and at least $1$ more at height $2$; here are two such trees.

              *                     *
             / \                   / \
            /   \                 /   \
           *     *               *     *
          / \                         /
         *   *                       *

If you can figure out how many of these there are altogether, you can add that to the $6$ already found to get the correct total. (There is a simple way to calculate it without simply drawing all of them.)