Which sequence is the pre-order traversal of the BST formed by inserting the…
2018
Which sequence is the pre-order traversal of the BST formed by inserting the following keys in the given order?
9, 8, 12, 22, 4, 10, 13
- A.
8, 9, 4, 12, 10, 22, 13
- B.
9, 8, 4, 12, 22, 10, 13
- C.
9, 8, 4, 12, 10, 22, 13
- D.
13, 22, 10, 12, 4, 8, 9
Attempted by 149 students.
Show answer & explanation
Correct answer: C
Construct the BST by inserting the keys in the given order:
1. 9 becomes the root.
2. 8 is inserted to the left of 9.
3. 12 is inserted to the right of 9.
4. 22 is inserted to the right of 12.
5. 4 is inserted to the left of 8.
6. 10 is inserted to the left of 12.
7. 13 is inserted to the left of 22.
Now take pre-order traversal: root, left subtree, right subtree.
Pre-order = 9, 8, 4, 12, 10, 22, 13.
Correct Answer: Option C.