Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order…
2009
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 inorder 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 316 students.
Show answer & explanation
Correct answer: C
In a binary search tree (BST), the inorder traversal always visits nodes in ascending order.
Regardless of the insertion sequence, the inorder traversal will yield all elements sorted. The given numbers are 7, 5, 1, 8, 3, 6, 0, 9, 4, 2. Sorting these values results in the sequence: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.