Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order…
2003
Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order into an initially empty binary search tree. The binary search tree uses the usual ordering on natural numbers. What is the in-order traversal sequence of the resultant tree ?
- A.
7 5 1 0 3 2 4 6 8 9
- B.
0 2 4 3 1 6 5 9 8 7
- C.
0 1 2 3 4 5 6 7 8 9
- D.
9 8 6 4 2 3 0 1 5 7
Attempted by 415 students.
Show answer & explanation
Correct answer: C
Key insight: in-order traversal of a binary search tree visits the left subtree first, then the node, then the right subtree.
Because the tree is a binary search tree, an in-order traversal always produces the node values in ascending (sorted) order.
All integers from 0 through 9 are present in the tree after the given insertions, so the sorted ascending sequence is the consecutive numbers 0 through 9.
Therefore the in-order traversal sequence is: 0 1 2 3 4 5 6 7 8 9
A video solution is available for this question — log in and enroll to watch it.