The maximum number of binary trees that can be formed with three unlabeled…

Solution: The number of distinct unlabeled rooted binary trees with n nodes is the nth Catalan number.

Use the formula C_n = (1/(n+1)) * binomial(2n, n). For n = 3:

C3 = (1/4) * binomial(6,3) = (1/4) * 20 = 5.

Therefore there are 5 distinct binary tree shapes with three unlabeled nodes. These shapes can be described as:

• A chain of three nodes leaning left (root with a left child, which has a left child).

• A chain of three nodes leaning right (root with a right child, which has a right child).

• A zig-zag left-right (root → left child → right child).

• A zig-zag right-left (root → right child → left child).

• A root with two children (one left and one right child).