ITPEC FE Subject A April 2025 Question 5
Among the four tree traversal techniques—breadth-first, in-order, post-order, and pre-order—which of the following is the appropriate combination to ensure that the last two nodes visited are the same in the tree shown below, when the left child is explored first?
Explanation
In-order and pre-order — both traversals end with 20 and then 22.
The tree: root 18; left child 5 with left child 3; right child 20 with right child 22. Visiting the left child first:
- •Breadth-first: 18, 5, 20, 3, 22, ending 3, 22
- •Pre-order (node, left, right): 18, 5, 3, 20, 22, ending 20, 22
- •In-order (left, node, right): 3, 5, 18, 20, 22, ending 20, 22
- •Post-order (left, right, node): 3, 5, 22, 20, 18, ending 20, 18
They agree because the right subtree 20 → 22 has no left children, so both finish by visiting 20 and then its right child 22.
Answer (d)
Why not others:
- •(a) Breadth-first and post-order — end 3, 22 and 20, 18, so neither node matches
- •(b) Breadth-first and pre-order — breadth-first ends on the bottom level, 3 then 22, while pre-order ends 20, 22
- •(c) In-order and post-order — post-order visits the root 18 last, so it ends 20, 18, not 20, 22
Key rule: Post-order always ends at the root, breadth-first ends on the deepest level, and in-order always ends at the rightmost node; write each traversal out in full before comparing.
Algorithm and Programming · AI-written, may contain errors
This question comes from an official ITPEC past paper. ITPEC Practice is an independent study tool and is not affiliated with ITPEC. See the official FE past-paper collection or Report an issue.