# How many permutations for generating a specific binary search tree?

The keys 2, 4, 6, 7, and 8 have been inserted, one by one, in some unknown order, into an initially empty BST. The result is this BST:

There are 120 different permutations of the five keys, but not all of these would lead to this particular BST being built. How many of the permutations will generate this particular BST?

In a BST we can't say anything regarding the order of elements that are on separate sides of a node (e.g. 4 and 8, because they are on separate sides of node 6), however, we know that if a node is a parent of another node, it must have been inserted before it.

So 6 is always going to be the first element. Then either 4 or 7 can come (two choices). Then if we look at the remaining structure, 4/2 and 7/8 have exactly the same structure, so we can analyze just one.

Without loss of generality, assume we picked 4. Afterwards we can choose either 2 or 7 (two choices).

If we chose 2, no choice is left. However if we chose 7 either 2 or 8 can come next (two choices). Then we're left with no choice.

So the total number of permutations is $2(1 + 2) = 6$. The permutations are:

64278
64728
64782
67842
67428
67482

• The sequences 4,2 and 7,8 can be shuffled. That gives ${4 \choose 2} = 6$ permutations (without listing them). – Hendrik Jan May 6 '17 at 11:52