For keys ordered C < B < A, which of the following binary search trees is…

Concept

An optimal binary search tree minimizes the probability-weighted search path length.

Successful searches end at key nodes, while unsuccessful searches end at external leaves; therefore both key levels and external-leaf levels contribute to the cost.

Application

1. The diagrams use the key order C < B < A. There are three successful-search outcomes and four unsuccessful-search outcomes.

2. Because all seven probabilities are equal, the common probability factor can be omitted. It is enough to compare the sum of the displayed levels of the three key nodes and four external leaves.

3. Each unbalanced tree has key-level sum 1 + 2 + 3 = 6 and external-leaf-level sum 2 + 3 + 4 + 4 = 13, giving a total of 19.

4. The balanced tree rooted at B has key-level sum 1 + 2 + 2 = 5 and external-leaf-level sum 3 + 3 + 3 + 3 = 12, giving a total of 17.

5. Since 17 is smaller than 19, the minimum expected cost is obtained by the tree rooted at B, with C on the left and A on the right.

Cross-check

With equal probabilities, symmetry places the median key at the root and leaves one key in each subtree. B is the median of C < B < A, so the same balanced tree follows independently. If a convention counts an unsuccessful search at the parent of an external leaf, it subtracts the same constant from every candidate and does not change this comparison.

Therefore, the optimal tree is the one rooted at B with C as its left child and A as its right child.