Permutation of keys inserted into a tree?

Question

Give the fraction of permutations of the keys $A $ through $G$ that will, when inserted into an initially empty tree, produce the same Binary search tree as does $A$ $E$ $F$ $G$ $B$ $D$ $C$

ANSWER:

(5 C 2) /7! = 10/5040 = 1/504.

Anyone has a clue on how we came up with this answer?

Answer 1

When you have a given binary search tree, the possible insertion sequences that will produce that tree is exactly every sequence where an internal node comes before all of its descendants in the tree.

So in this case, the sequence must start with A E, F must come before G, and B, D, C occur in that order between themselves.

But we're free to choose how we merge the sublists F G and B C D to produce the final sequence. Once we have written down A E, we can choose any $2$ of the remaining $5$ positions to be F and G, and the last three then become B, D and C, in that order.

Therefore there are $\binom52=10$ different input sequences that produce your given tree.

Answer 2

Clearly the first key in the permutation must be $A$, since that determines the root of the derived tree. The second key will be a child of $A$, so it must be $E$. Similarly, the third key must be one of $B$ and $F$. Let’s take a closer look at the string consisting of the last five keys.

• It must begin with $B$ or $F$.
• $B$ must precede both $C$ and $D$.
• $D$ must precede $C$, as otherwise $C$ would be a child of $B$.
• $F$ must precede $G$.

That boils down to saying that $B,D$, and $C$ must appear in that order, and that $F$ and $G$ must appear in that order, but the strings $BDC$ and $FG$ can be interlaced arbitrarily. Thus, once we decide which two of the last five keys are $F$ and $G$, we’ve completely determined the order of the keys: if the last five keys are, for instance, $??FG?$, then they must be $BDFGC$. There are $\binom52$ ways to choose two of the five positions to be filled by $F$ and $G$, so there are $\binom52$ possible permutations that yield the desired tree.