ITPEC FE Subject A April 2024 Question 5

Post-order Traversal of a Binary Tree — identify the correct post-order sequence.

Post-order rule: Left → Right → Root (visit children before the node itself).

Tree structure:
- Root: 10
- Left subtree: 3 → left 2, right 7 → 7 has left 4, right 8
- Right subtree: 13 → left 15, right 18

Step-by-step traversal:
- Visit left subtree of 10: process subtree rooted at 3
- Visit left of 3: 2 (leaf)
- Visit right of 3: process subtree rooted at 7
- Left of 7: 4 (leaf)
- Right of 7: 8 (leaf)
- Node: 7
- Node: 3
- Visit right subtree of 10: process subtree rooted at 13
- Left of 13: 15 (leaf)
- Right of 13: 18 (leaf)
- Node: 13
- Visit root: 10

Result: 2, 4, 8, 7, 3, 15, 18, 13, 10 → (b)

Why not others:
- (a) 2, 3, 4, 7, 8, 10, 13, 15, 18 — this is in-order traversal (Left → Root → Right), producing sorted output for a BST
- (c) 10, 3, 2, 7, 4, 8, 13, 18, 15 — this is pre-order traversal (Root → Left → Right)
- (d) 10, 3, 13, 2, 7, 18, 4, 8, 15 — incorrect order, does not match any standard traversal

Key rule: In post-order, the root is always the last element. In pre-order, the root is always the first.

AI-generated — may contain errors