Consider a binary search tree (BST) with π leaf nodes (π > 0). Given anyβ¦
2026
Consider a binary search tree (BST) with π leaf nodes (π > 0). Given any node π, the key present in the node is denoted as πππ(π). All the keys present in the given BST are distinct. The keys belong to the set of real numbers. For a node π, let ππ’π(π) denote the node that is its inorder successor. If a node π does not have an inorder successor, then ππ’π(π) is πππΏπΏ. As there are no duplicates, if ππ’π(π) is not πππΏπΏ, then πππ(π) < πππ(ππ’π(π)).
Corresponding to every leaf node πΏπ that has a non-NULL ππ’π(πΏπ), a new key ππ with the following property is to be inserted into the BST.
πππ(πΏπ) < ππ < πππ(ππ’π(πΏπ))
Let πΎ represent the list of all such new keys to be inserted into the BST. Which of the following statements is/are true?
Answer: A. K cannot have any duplicates; C. After inserting all keys from πΎ, the height of the BST can increase at most by one β ConceptInorder traversal of a BST with distinct keys lists the keys in strictly increasing order. Therefore a node and its inorder successor are consecutiveβ¦
- A.
K cannot have any duplicates
- B.
K will have at least one element
- C.
After inserting all keys from πΎ, the height of the BST can increase at most by one
- D.
Number of nodes in the BST will double after inserting all keys from K
Attempted by 38 students.
Show answer & explanation
Correct answer: A, C
Concept
Inorder traversal of a BST with distinct keys lists the keys in strictly increasing order. Therefore a node and its inorder successor are consecutive in that order, and the open intervals between different consecutive pairs have disjoint interiors.
If a new key lies strictly between a leaf key and that leafβs successor, the BST search follows the original path to the leaf and places the new key as its right child. The governing assumptions are that the original keys are distinct and every kα΅’ is chosen from the interval specified for its original leaf.
Application
For every eligible leaf Lα΅’, the rule gives Val(Lα΅’) < kα΅’ < Val(Suc(Lα΅’)). Because distinct leaves determine distinct consecutive-key intervals with no common interior, two chosen keys cannot coincide. Hence K cannot contain duplicates.
The condition n > 0 does not force an eligible leaf. In a one-node BST, the only leaf is also the maximum node, so its inorder successor is NULL and K is empty. Hence K need not contain an element.
For each eligible Lα΅’, searching for kα΅’ ends at Lα΅’ and inserts kα΅’ as its right child. Keys for other leaves lie in disjoint intervals, so none is inserted below a newly added key. Every original root-to-leaf path is therefore extended by at most one edge, and the height increases by at most one.
Let N be the original total number of nodes. The construction adds at most n nodes, whereas every nontrivial BST has internal nodes as well as its n leaves, so N > n. Thus the final count N + |K| is less than 2N; in the one-node case |K| = 0. The node count does not double.
Cross-check and contrast
For the BST with root 2 and leaves 1 and 3, only leaf 1 has a successor. Choosing k in (1, 2) inserts it as the right child of 1, produces one distinct new key, and extends the height by one.
For a one-node BST, K is empty and the height and node count remain unchanged.
The two examples cover both the nonempty and empty forms of K and agree with the interval and insertion-path arguments.
Result
The true statements are βK cannot have any duplicatesβ and βAfter inserting all keys from K, the height of the BST can increase at most by one.β