The preorder traversal of a binary search tree is 15, 10, 12, 11, 20, 18, 16, 19. Which one of the following is the postorder traversal of the tree?

Correct option is B

To determine the postorder traversal, we must first construct the Binary Search Tree (BST) from the given preorder traversal and then perform postorder traversal.
Step 1: Constructing the BST from Preorder Traversal
Given Preorder: 15, 10, 12, 11, 20, 18, 16, 19
· First Element (Root): 15
· Elements smaller than 15 go to the left subtree: 10, 12, 11
· Elements greater than 15 go to the right subtree: 20, 18, 16, 19
The BST structure:
15
/ \
10 20
\ /
12 18
/ / \
11 16 19
Step 2: Postorder Traversal
Postorder traversal follows the Left → Right → Root order.
1. Left Subtree (10):
· Left child: None
· Right child (12):
· Left child (11) → Visit 11
· Root (12) → Visit 12
· Root (10) → Visit 10
2. Right Subtree (20):
· Left child (18):
· Left child (16) → Visit 16
· Right child (19) → Visit 19
· Root (18) → Visit 18
· Root (20) → Visit 20
3. Root Node (15) → Visit 15
Final Postorder Sequence:
11, 12, 10, 16, 19, 18, 20, 15
Since this matches option (b), the correct answer is (b) 11, 12, 10, 16, 19, 18, 20, 15.
Important Key Points:
1. Preorder Traversal (Root → Left → Right) helps in constructing the BST.
2. Postorder Traversal (Left → Right → Root) visits the left subtree first, then the right subtree, and finally the root.
3. BST Construction Rules:
· Left child < Parent
· Right child > Parent
4. Understanding Postorder Traversal Output:
· First, visit all left subtree nodes.
· Then, visit all right subtree nodes.
· Finally, visit the root node.
5. Application of Postorder Traversal:
· Used in deleting nodes from a tree.
· Used in expression tree evaluations (postfix notation).