ITPEC FE Morning April 2023 Question 7

9, 3, 1, 6, 4, 7, 10, 14, 13 — pre-order visits a node first, then its left subtree, then its right subtree.

Trace from the root:

• •Visit 9, then go into its left subtree, rooted at 3
• •Visit 3, then its left child 1 (a leaf), then its right subtree, rooted at 6
• •Visit 6, then its children 4 and 7
• •Back at the root, go into the right subtree: visit 10; it has no left child, so visit its right child 14, then 14's left child 13

Answer (c)

Why not others:

• •(a) — the in-order traversal (left, node, right); for this binary search tree it lists the keys in ascending order
• •(b) — the post-order traversal (left, right, node), which ends at the root
• •(d) — the level-order traversal, which reads the tree row by row from the top

Key rule: The root's position identifies the traversal: first in pre-order, last in post-order, and between its two subtrees in in-order.

Algorithm and Programming · AI-written, may contain errors