Preorder traversal of binary search tree is 38, 14, 8, 23, 18, 20, 56, 45, 82,…
2021
Preorder traversal of binary search tree is 38, 14, 8, 23, 18, 20, 56, 45, 82, 70. What is the postorder traversal of the binary search tree?
- A.
23, 20, 18, 14, 8, 38, 45, 56, 70, 82
- B.
8, 18, 20, 23, 14, 45, 70, 82, 56, 38
- C.
8, 20, 18, 23, 14, 45, 70, 82, 56, 38
- D.
82, 70, 56, 45, 38, 23, 20, 18, 14, 8
Attempted by 218 students.
Show answer & explanation
Correct answer: C
Step 1: In preorder traversal, the first element is the root of the tree. So, 38 is the root.
Step 2: In a binary search tree, all values in the left subtree are less than the root, and all values in the right subtree are greater than the root.
Step 3: From the preorder sequence: 38, 14, 8, 23, 18, 20, 56, 45, 82, 70.
Step 4: Left subtree of 38: 14, 8, 23, 18, 20 (all < 38).
Step 5: Right subtree of 38: 56, 45, 82, 70 (all > 38).
Step 6: Recursively apply preorder logic to left subtree: 14 is root of left subtree.
Step 7: Left of 14: 8 (< 14), Right of 14: 23, 18, 20 (> 14).
Step 8: 23 is root of right subtree of 14. Left of 23: 18, 20. 18 is root and 20 is its right child.
Step 9: Recursively apply preorder logic to right subtree: 56 is root of right subtree.
Step 10: Left of 56: 45 (< 56), Right of 56: 82, 70 (> 56).
Step 11: 82 is root of right subtree of 56. Left of 82: 70, Right: none.
Step 12: Postorder traversal visits left subtree, then right subtree, then root.
Step 13: Postorder of left subtree of 38: 8, 20, 18, 23, 14.
Step 14: Postorder of right subtree of 38: 45, 70, 82, 56.
Step 15: Final postorder traversal: 8, 20, 18, 23, 14, 45, 70, 82, 56, 38.