IPA FE Subject A 2025 Question 3

d < b < e < a < f < c < g — in a binary search tree, an in-order traversal (left subtree, node, right subtree) visits the values in ascending order.

In a binary search tree, every value in a node's left subtree is smaller than the node and every value in its right subtree is larger. So:

• •Under b: d < b < e
• •Under c: f < c < g
• •Under a: the whole left subtree d, b, e < a < the whole right subtree f, c, g

Putting these together gives d < b < e < a < f < c < g, the in-order sequence of the tree.

Answer (b)

Why not others:

• •(a) — the pre-order sequence (node before its subtrees); it makes a the smallest, but b is in a's left subtree, so b < a
• •(c) — lists the leaves, then b and c, then the root, as if every parent were larger than its children; but f, c and g are in a's right subtree, so they are larger than a
• •(d) — the sequence of (a) reversed; it makes g the smallest, but g is the rightmost node and so the largest

Key rule: In a binary search tree, left < node < right holds for whole subtrees, so the in-order traversal lists the keys in ascending order.

Algorithm and Programming · AI-written, may contain errors