A binary search tree contains the value 1,2,3,4,5,6,7,8. The tree is traversed…
1997
A binary search tree contains the value 1,2,3,4,5,6,7,8. The tree is traversed in pre-order and the values are printed out. Which of the following sequences is a valid output?
- A.
5 3 1 2 4 7 8 6
- B.
5 3 1 2 6 4 8 7
- C.
5 3 2 4 1 6 7 8
- D.
5 3 1 2 4 7 6 8
Attempted by 31 students.
Show answer & explanation
Correct answer: D
In a pre-order traversal, the root is visited first, followed by the left subtree and then the right subtree. For a Binary Search Tree, all values in the left subtree must be smaller than the root, and all values in the right subtree must be larger. Verify each sequence by ensuring these constraints hold recursively for every node.
A video solution is available for this question — log in and enroll to watch it.