Consider a binary search tree (BST) with π leaf nodes (π > 0). Given anyβ¦
GATE Β· 2026 Β· CS Β· Set 2 Β· Computer Science & IT
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?
- 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 72 students.
Sign up free to check your answer
Sign up freeLoading lessonβ¦