ITPEC FE Subject A April 2024 Question 5

2, 4, 8, 7, 3, 15, 18, 13, 10 — post-order visits the left subtree, then the right subtree, then the node itself.

The tree: 10 has children 3 and 13; 3 has children 2 and 7; 7 has children 4 and 8; 13 has only a right child, 18; 18 has only a left child, 15.

• •Left subtree of 10 (rooted at 3): 2, then the subtree at 7 gives 4, 8, 7, then 3
• •Right subtree of 10 (rooted at 13): no left child; the subtree at 18 gives 15, 18; then 13
• •The root comes last: 10

Answer (b)

Why not others:

• •(a) — in-order (left, node, right); for this binary search tree it lists the keys in ascending order
• •(c) — pre-order (node, left, right), which puts the root first
• •(d) — level-order (breadth-first): 10, then 3, 13, then 2, 7, 18, then 4, 8, 15

Key rule: Pre-order puts the root first, post-order puts it last, in-order of a binary search tree gives the sorted keys, and level-order reads the tree row by row.

Algorithm and Programming · AI-written, may contain errors