GATE CS 2007 Q13 — Trees

The number of structurally unique binary trees that can be formed with $n$ unlabeled nodes is given by the $n^{\text{th}}$ Catalan number, $C_n$:

For $n = 3$ unlabeled nodes, we calculate $C_3$ as follows:

The $5$ distinct structural shapes of these binary trees are:

1. Left-skewed (straight): Root $\rightarrow$ Left $\rightarrow$ Left
2. Left-skewed (zigzag): Root $\rightarrow$ Left $\rightarrow$ Right
3. Balanced: Root with one Left child and one Right child
4. Right-skewed (zigzag): Root $\rightarrow$ Right $\rightarrow$ Left
5. Right-skewed (straight): Root $\rightarrow$ Right $\rightarrow$ Right

Thus, the maximum number of binary trees that can be formed is 5.