How many different binary trees can be built from three nodes A, B and C?
30: there are 5 different shapes of a binary tree with three nodes, and each shape can be labelled with A, B and C in $3! = 6$ ways, so $5 \times 6 = 30$.
* Left-left, left-right, balanced, right-left and right-right: five shapes, each with 6 labellings. *
Counting the shapes. One node is the root. The remaining two are split between its left and right subtree:
- Both on the left (2 + 0): the left subtree has two nodes, and its own second node can hang left or right. 2 shapes.
- One on each side (1 + 1): 1 shape, the balanced one.
- Both on the right (0 + 2): again 2 shapes.
That is $2 + 1 + 2 = 5$ shapes. The left/right distinction is what makes it five: a root with a single left child and a root with a single right child are different binary trees.
Counting the labellings. Each shape has three positions, and A, B and C can be assigned to them in $3! = 6$ orders.
So there are $5 \cdot 6 = 30$ binary trees. The lesson is that the same three keys, inserted or rearranged in a different order, can produce very different trees.
Go deeper:
Catalan number — the sequence 1, 1, 2, 5, 14, … that counts binary tree shapes with $n$ nodes.