The number of distinct binary trees that can be formed with 5 nodes is

Concept

The number of distinct binary tree shapes on n unlabelled nodes is the n-th Catalan number Cn. A binary tree is fixed by choosing its root and then splitting the remaining n − 1 nodes into a left subtree and a right subtree, each of which is itself a binary tree.

That recursive split gives the recurrence Cn = C0Cn−1 + C1Cn−2 + … + Cn−1C0, with C0 = 1 for the empty tree, and the closed form Cn = (1/(n + 1)) · (2n)! / (n! · n!).

Application

Here n = 5, so build the Catalan values upward from the base case.

1. C0 = 1 (the empty tree) and C1 = 1 (a single node).

2. C2 = C0C1 + C1C0 = 1 + 1 = 2.

3. C3 = C0C2 + C1C1 + C2C0 = 2 + 1 + 2 = 5.

4. C4 = C0C3 + C1C2 + C2C1 + C3C0 = 5 + 2 + 2 + 5 = 14.

5. C5 = C0C4 + C1C3 + C2C2 + C3C1 + C4C0 = 14 + 5 + 4 + 5 + 14 = 42.

Cross-check

The closed form must agree: C5 = (1/6) · 10! / (5! · 5!) = (1/6) · 252 = 42. Both routes give 42 distinct binary tree shapes on 5 nodes.

Contrast with the other values

Note on the reading: the count is over shapes (unlabelled nodes), the standard convention for this question. With five distinct labelled keys the answer would instead be 5! × C5 = 5040, which is not among the values offered.