A binary search tree contains the numbers 1, 2, 3, 4, 5, 6, 7, 8. When the…
2005
A binary search tree contains the numbers 1, 2, 3, 4, 5, 6, 7, 8. When the tree is traversed in pre-order and the values in each node printed out, the sequence of values obtained is 5, 3, 1, 2, 4, 6, 8, 7. If the tree is traversed in post-order, the sequence obtained would be
- A.
8, 7, 6, 5, 4, 3, 2, 1
- B.
1, 2, 3, 4, 8, 7, 6, 5
- C.
2, 1, 4, 3, 6, 7, 8, 5
- D.
2, 1, 4, 3, 7, 8, 6, 5
Attempted by 210 students.
Show answer & explanation
Correct answer: D
Key idea: Preorder lists nodes as root, then left subtree, then right subtree. Post-order lists nodes as left subtree, then right subtree, then root. Use the preorder to reconstruct the tree structure, then read off the post-order.
Root: The first preorder value is 5, so 5 is the tree root.
Left subtree preorder: the values less than 5 that follow are 3, 1, 2, 4. So the left subtree has root 3 with preorder 3,1,2,4.
Reconstruct left subtree: 3 is root; values less than 3 are 1,2 (preorder 1,2) which form a subtree with root 1 and right child 2; value 4 is right child of 3. So left-subtree structure yields post-order 2, 1, 4, 3.
Right subtree preorder: the values greater than 5 that follow are 6, 8, 7. So the right subtree has root 6 with preorder 6,8,7.
Reconstruct right subtree: 6 is root; remaining preorder 8,7 places 8 as right child of 6 and 7 as left child of 8. That subtree's post-order is 7, 8, 6.
Combine left and right post-orders and then the root: left-subtree post-order (2, 1, 4, 3), right-subtree post-order (7, 8, 6), then root 5.
Answer: 2, 1, 4, 3, 7, 8, 6, 5