Question 49

Let us check each statement:

• (A) is true: For any two distinct nodes $u$ and $v$ with $Val(u) < Val(v)$, since $Suc(u)$ is the smallest key in the BST strictly greater than $Val(u)$, we have $Val(u) < Val(Suc(u)) \le Val(v) < Val(Suc(v))$. Hence the open intervals $(Val(L_i), Val(Suc(L_i)))$ are pairwise disjoint, so no two $k_i$ can be equal.
• (B) is false: If the BST has only 1 node (or is a left-skewed chain where the single leaf is the maximum element in the tree), that leaf has $Suc(L_1) = NULL$, so $K$ is empty.
• (C) is true: Because $L_i$ is a leaf and $Val(L_i) < k_i < Val(Suc(L_i))$, no existing key in the BST lies between $Val(L_i)$ and $k_i$, and $L_i$ has no children. When $k_i$ is inserted into the BST, the search path must reach $L_i$ and attach $k_i$ as the right child of $L_i$. Since at most one key $k_i$ is generated per leaf $L_i$, each existing leaf receives at most one right child, so the height of the BST increases by at most $1$.
• (D) is false: At most $n$ keys are inserted (where $n$ is the number of leaves), which is strictly less than the total number of nodes in any BST with $\ge 1$ node.