A Binary Search Tree (BST) is constructed by inserting the following elements…
2024
A Binary Search Tree (BST) is constructed by inserting the following elements in the given order:
46, 72, 39, 58, 21, 13, 65, 87, 99
What will be the inorder traversal of the BST?
- A.
46, 39, 21, 13, 72, 58, 65, 87, 99
- B.
13, 21, 39, 46, 58, 65, 72, 87, 99
- C.
99, 87, 72, 65, 58, 46, 39, 21, 13
- D.
13, 39, 21, 46, 58, 72, 65, 87, 99
- E.
21, 13, 39, 46, 65, 58, 72, 99, 87
Attempted by 34 students.
Show answer & explanation
Correct answer: B
Key idea: the in-order traversal of any Binary Search Tree (BST) visits the nodes in non-decreasing (ascending) order. This follows directly from the BST property — for every node, all keys in its left subtree are smaller and all keys in its right subtree are larger, and in-order visits left subtree, then the node, then the right subtree.
So you do not even need to draw the tree: the in-order traversal is simply the input values sorted in ascending order.
Sorting 46, 72, 39, 58, 21, 13, 65, 87, 99 gives:
13, 21, 39, 46, 58, 65, 72, 87, 99
For reference, building the BST (root 46) and reading it left-root-right gives the same sequence. Note that the pre-order traversal of this tree is 46, 39, 21, 13, 72, 58, 65, 87, 99 and the reverse in-order (descending) is 99, 87, 72, 65, 58, 46, 39, 21, 13 — both are common distractors.