ITPEC FE Subject A October 2024 Question 5

20 — the in-order traversal gives ((2 + 3) × 10 − 10) ÷ 2, each subtree acting as a parenthesised operand.

In-order visits the left subtree, the node, then the right subtree. Operators are internal nodes and operands are leaves, so every subtree is computed before its parent's operator:

• •the + node: 2 + 3 = 5
• •the × (*) node: 5 × 10 = 50
• •the − node: 50 − 10 = 40
• •the / root: 40 ÷ 2 = 20

Answer (b)

Why not others:

• •(c) 27 — reads the sequence as 2 + 3 × 10 − 10 ÷ 2 without the tree's grouping, using normal precedence: 2 + 30 − 5 = 27
• •(d) 45 — keeps (2 + 3) × 10 = 50 but lets the division apply to the second 10 only: 50 − 10 ÷ 2 = 45
• •(a) 11 — divides the whole left side by 2 but uses normal precedence inside it: (2 + 3 × 10 − 10) ÷ 2 = 22 ÷ 2 = 11

Key rule: An expression tree carries its own precedence, a lower node is always computed first, so writing an in-order traversal as infix needs parentheses around every subtree.

Algorithm and Programming · AI-written, may contain errors