How many different binary trees are possible with 8 nodes?

Formula: The number of different binary trees with n nodes equals the nth Catalan number,

C_n = 1/(n+1) * (2n choose n).

Compute for n = 8:

1. Step 1: Calculate the binomial coefficient (2n choose n) = (16 choose 8) = 12870.

2. Step 2: Apply the Catalan formula: C_8 = 1/(8+1) * 12870 = 12870 / 9 = 1430.

Answer: There are 1430 different binary trees with 8 nodes.

------------------------------------------------------------------------------------------------------

The Core Idea: Splitting the Nodes

Every binary tree has exactly one root node at the very top.

If you have n nodes total, and you use 1 for the root, you have n - 1 nodes left over. These leftover nodes must be split between the left branch and the right branch.

To find the total number of possible trees, you look at every possible way to split those leftover nodes, find out how many tree shapes each side can make, and multiply them together.

Building from Scratch (Starting with 0)

Let's call the number of possible trees for a given number of nodes T(n).

0 Nodes: T(0) = 1

If you have 0 nodes, there is only 1 way to draw it: an empty space. (This might sound weird, but it's mathematically necessary for the next steps!)

1 Node: T(1) = 1

If you have 1 node, it is just the root. There is exactly 1 way to draw this.

2 Nodes: T(2) = 2

You use 1 node for the root, leaving 1 node. You can split that 1 leftover node two ways:

1 on the left, 0 on the right: (1 way for left × 1 way for right) = 1
0 on the left, 1 on the right: (1 way for left × 1 way for right) = 1
Total: 1 + 1 = 2 ways.

3 Nodes: T(3) = 5

You use 1 node for the root, leaving 2 nodes. You can split them:

2 on left, 0 on right: (T(2) ways × T(0) ways) → 2 × 1 = 2
1 on left, 1 on right: (T(1) ways × T(1) ways) → 1 × 1 = 1
0 on left, 2 on right: (T(0) ways × T(2) ways) → 1 × 2 = 2
Total: 2 + 1 + 2 = 5 ways.

Finding the Pattern

Do you see the pattern? For any number of nodes, we just pair up the answers from the smaller trees we already calculated. We multiply the outer numbers, move inward, multiply those, and add them all up.

Let's use our known list so far: 1, 1, 2, 5 (for 0, 1, 2, and 3 nodes).

4 Nodes: T(4) (Leaves 3 nodes to split)

(Left 3, Right 0): 5 × 1 = 5
(Left 2, Right 1): 2 × 1 = 2
(Left 1, Right 2): 1 × 2 = 2
(Left 0, Right 3): 1 × 5 = 5
Total T(4) = 5 + 2 + 2 + 5 = 14

5 Nodes: T(5) (Leaves 4 nodes to split)

(14 × 1) + (5 × 1) + (2 × 2) + (1 × 5) + (1 × 14)
14 + 5 + 4 + 5 + 14 = 42

6 Nodes: T(6) (Leaves 5 nodes to split)

(42 × 1) + (14 × 1) + (5 × 2) + (2 × 5) + (1 × 14) + (1 × 42)
42 + 14 + 10 + 10 + 14 + 42 = 132

7 Nodes: T(7) (Leaves 6 nodes to split)

(132 × 1) + (42 × 1) + (14 × 2) + (5 × 5) + (2 × 14) + (1 × 42) + (1 × 132)
132 + 42 + 28 + 25 + 28 + 42 + 132 = 429

8 Nodes: T(8) (Leaves 7 nodes to split)

(429 × 1) + (132 × 1) + (42 × 2) + (14 × 5) + (5 × 14) + (2 × 42) + (1 × 132) + (1 × 429)
429 + 132 + 84 + 70 + 70 + 84 + 132 + 429 = 1430