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.
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:
In any optimal binary search tree the leaves are the dummy variables and the dummy variables are leaves.
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.
