TAOCP 6.2.2 Exercise 5

Section 6.2.2: Binary Tree Searching

Exercise 5. [M25] [M25] There are 11! = 39,916,800 different orders in which the names CAPRICORN, AQUARIUS, etc. could have been inserted into a binary search tree. a) How many of these arrangements will produce Fig. 10? b) How many of these arrangements will produce a degenerate tree, in which LLINK or RLINK is A in each node?

Verified: yes
Solve time: 1m46s

---

Solution

Let $T$ be the binary search tree obtained when the keys are inserted in the order

$$ \text{CAPRICORN},\ \text{AQUARIUS},\ \text{ARIES},\ \text{TAURUS},\ \text{CANCER},\ \text{SCORPIO},\ \text{PISCES},\ \text{GEMINI},\ \text{LIBRA},\ \text{LEO},\ \text{VIRGO}. $$

For a fixed binary search tree shape, the number of insertion orders that produce it equals the product over all nodes $x$ of the binomial coefficient

$$ \binom{L_x+R_x}{L_x}, $$

where $L_x$ and $R_x$ are the sizes of the left and right subtrees of $x$. This follows from the fact that, once the root is fixed, the relative order of keys in the left and right subtrees may be interleaved arbitrarily while preserving internal order constraints, and the process repeats independently in each subtree.

Structure of Fig. 10

The root is CAPRICORN.

The left subtree contains the keys

$$ {\text{AQUARIUS},\ \text{ARIES},\ \text{CANCER}}, $$

and the right subtree contains the remaining eight keys except CAPRICORN:

$$ {\text{TAURUS},\ \text{SCORPIO},\ \text{PISCES},\ \text{GEMINI},\ \text{LIBRA},\ \text{LEO},\ \text{VIRGO}}. $$

The left subtree has the form

AQUARIUS with right child ARIES and ARIES with right child CANCER. Each node in this subtree has a single child, so every binomial factor in this subtree equals $1$, and the subtree contributes a factor $1$.

The right subtree is rooted at TAURUS. Its left subtree is rooted at PISCES and its right subtree is SCORPIO.

At TAURUS, the left subtree has $5$ nodes (PISCES subtree) and the right subtree has $1$ node (SCORPIO), so the contribution is

$$ \binom{5+1}{5}=\binom{6}{5}=6. $$

The subtree rooted at PISCES has left subtree GEMINI of size $1$ and right subtree rooted at LIBRA of size $3$, so its contribution is

$$ \binom{1+3}{1}=\binom{4}{1}=4. $$

The subtree rooted at LIBRA has right subtree LEO of size $2$ and no left subtree, so its contribution is

$$ \binom{2}{0}=1. $$

The subtree rooted at LEO has right child VIRGO and no left subtree, so its contribution is

$$ \binom{1}{0}=1. $$

The subtree rooted at GEMINI and SCORPIO contribute $1$ each since they are leaves.

Thus the right subtree contributes

$$ 6 \cdot 4 \cdot 1 \cdot 1 = 24. $$

At the root CAPRICORN, the left subtree has $3$ nodes and the right subtree has $7$ nodes, so the root contribution is

$$ \binom{3+7}{3}=\binom{10}{3}=120. $$

Multiplying all contributions gives

$$ 120 \cdot 24 = 2880. $$

Hence the number of insertion orders producing Fig. 10 equals

$$ \boxed{2880}. $$

(b) Degenerate trees

A degenerate binary search tree has the property that every node has either LLINK or RLINK equal to $A$, so the tree forms a single chain.

Consider any permutation of $n$ distinct keys. During insertion, the tree remains a single path if and only if every newly inserted key is either strictly larger than all previous keys or strictly smaller than all previous keys. Otherwise, insertion would create a second branch at the first violation point.

After the first key is inserted arbitrarily, each subsequent key has exactly two admissible choices: it may become the new minimum or the new maximum among the keys seen so far. Each such choice uniquely determines its placement in the current chain.

Since these two choices are available independently for each of the remaining $n-1$ insertions, the total number of permutations producing a degenerate tree equals

$$ 2^{n-1}. $$

For $n=11$ keys, this gives

$$ 2^{10}=1024. $$

Thus the number of insertion orders producing a degenerate tree is

$$ \boxed{1024}. $$

This completes the solution. ∎