Q39

Consider a binary search tree (BST) with $n$ leaf nodes $(n>0)$. Given any node $V$, the key present in the node is denoted as $\operatorname{Val}(V)$. All the keys present in the given BST are distinct. The keys belong to the set of real numbers. For a node $V$, let $\operatorname{Suc}(V)$ denote the node that is its inorder successor. If a node $V$ does not have an inorder successor, then $\operatorname{Suc}(V)$ is $N U L L$. As there are no duplicates, if $\operatorname{Suc}(V)$ is not $N U L L$, then $\operatorname{Val}(V)<\operatorname{Val}(\operatorname{Suc}(V))$. Corresponding to every leaf node $L_{i}$ that has a non-NULL $\operatorname{Suc}\left(L_{i}\right)$, a new key $k_{i}$ with the following property is to be inserted into the BST.

$$\operatorname{Val}\left(L_{i}\right) < k_{i} < Val (\operatorname{Suc}(L_{i}))$$

Let $K$ represent the list of all such new keys to be inserted into the BST. Which of the following statements is/are true?