# Observations about the structure of an optimal Binary Search Tree

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$$.

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).

• The value being compared against at the node $v$. Jul 30, 2021 at 14:04
• Ahh. I get it. Thanks!
– D G
Jul 30, 2021 at 14:05
• Thank you. As for the second paragraph, I understand that my example does not contradict the contiguous range property, but the paragraph from the book that I quoted also specifies that every node $k_i$ should be an ancestor of the two dummy nodes $d_{i - 1}$ and $d_i$. This is the property which does not seem to be satisfied by my example. Jul 30, 2021 at 14:19
• That seems like a different question, which requires more context. Jul 30, 2021 at 14:20
• @user8171079 dummy nodes can not be internal nodes. They have to be the leaf nodes.
– D G
Jul 30, 2021 at 14:30