Observations about the structure of an optimal Binary Search Tree

Question

My question is about part 15.5 in CLRS (third edition)^*, on optimal binary search trees. I am confused about the following sentences:

Consider any subtree of a binary search tree. It must contain keys in a contiguous range $k_i, …, k_j$ for some $1 \leq i \leq j \leq n$. In addition, a subtree that contains keys $k_i, …, k_j$ must also have as its leaves the dummy keys $d_{i-1}, … d_j$.

(where $(k_j)_{j \in {[1,\ …,\ n]}}$ is a sorted sequence containing the keys of the nodes in the BST).

The chapter does not include proof of this statement, which does not seem obvious to me at all.

Moreover, I do not understand why the tree (key: $d_0$, right child: (key: $k_1$, right child: $d_1$)) — where $d_0$ is the dummy node corresponding to values strictly less than $k_1$ and $d_1$ is the dummy node corresponding to values strictly greater than $k_1$ — is not a satisfactory counterexample. It satisfies the BST property ($d_0 < k_1 < d_1$) and $k_1$ is not an ancestor of $d_0$.

---

* Introduction to Algorithms, Cormen, Leiserson, Rivest & Stein

Answer 1

Let us prove by induction on depth that for every node $v$, there exist $a_v,b_v$ (possibly $\pm \infty$) such that the input $x$ reaches $v$ iff $a_v < x < b_v$. This is true for the root since we can take $a_r = -\infty$ and $b_r = +\infty$. Now suppose that it is true for some node $v$, and let $v_<,v_>$ be its two children. Suppose that node $v$ compares $x$ to $c_v$. Then $x$ reaches $v_<$ if $a_v < x < c_v$ and $v_>$ if $c_v < x < b_v$ (I'm not sure what happens when $x = c_v$ — that depends on the exact definition of BST). This implies your stated property.

Your example has three nodes. The first contains the values $d_0,k_1,d_1$, the second contains the values $k_1,d_1$, the third contains the value $d_1$. All of these are contiguous ranges (which is a more concise way to state the property in your post).