This is a paragraph from the book CLRS:

What we need is known as an optimal binary search tree. Formally, we are given a sequence $K = (k_1, k_2, ..., k_n)$ of $n$ distinct keys in sorted order (so that $k_1 < k_2 < ... < k_n$), and we wish to build a binary search tree from these keys. For each key $k_i$, we have a probability $p_i$ that a search will be for $k_i$. Some searches may be for values not in $K$, and so we also have $n + 1$ “dummy keys” $d_0, d_1, d_2, d_n$ representing values not in $K$. In particular, $d_0$ represents all values less than $k_1$, $d_n$ represents all values greater than $k_n$, and for $i = 1, 2, ..., n - 1$, the dummy key $d_i$ represents all values between $k_i$ and $k_{i + 1}$. For each dummy key $d_i$, we have a probability $q_i$ that a search will correspond to $d_i$. Figure $15.9$ shows two binary search trees for a set of $n = 5$ keys. Each key $k_i$ is an internal node, and each dummy key $d_i$ is a leaf.

enter image description here

Now, looks like, without loss of generality, CLRS has restricted itself to (optimal) binary search trees whose leaves are dummy variables (and whose dummy variables are leaves). This suggests that one of these two statements must be true:

  1. In any optimal binary search tree the leaves are the dummy variables and the dummy variables are leaves.

  2. There exists some optimal binary search tree whose leaves are dummy variables and whose dummy variables are leaves. (and CLRS is going to find one of such trees in the following paragraphs. This tree might even be unique.)

The following paragraph also suggests that one of the previous statements must be true:

As with matrix-chain multiplication, exhaustive checking of all possibilities fails to yield an efficient algorithm. We can label the nodes of any $n$-node binary tree with the keys $k_1, k_2, ..., k_n$ to construct a binary search tree, and then add in the dummy keys as leaves. In Problem $12-4$, we saw that the number of binary trees with $n$ nodes is $\Omega(\frac{4^n}{n^{}\frac{3}{2}})$, and so we would have to examine an exponential number of binary search trees in an exhaustive search. Not surprisingly, we shall solve this problem with dynamic programming.

Which one is true? I strongly believe the second one is true.


1 Answer 1


I am afraid you put the cart before the horse sort of. It is not a question about which statement is true. Both statement do not make much sense since those dummy variables/leaves for them are not part of the binary search tree.

The dummy variables are used to represent the situations when "some searches may be for values not in $K$". At the time when we design/create/modify a binary search tree, no such "dummy variables" are included. Once we have a binary search tree, for the sake of explaining how a search might end up with, those dummy variables are "added". They can only appear as leaves by the definition of a binary search tree.

In other words, there are two trees. One is the binary search tree. The other tree is the tree of all possible search results on that binary search tree. The latter tree is completely determined by the former tree.

For the sake of brevity, the authors choose to use one tree to represent those two trees.

  • 1
    $\begingroup$ Excellent answer. $\endgroup$
    – Emad
    Dec 26, 2022 at 9:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.