Question bank › A-level Computer Science › Fundamentals of algorithms

Tree traversal and reverse Polish notation

Answer on paper first, then reveal the mark scheme one mark at a time.

1Standard5 marks

The binary tree below stores integers.

(a) Write the order in which the nodes are visited in a pre-order traversal. [1]

(b) Write the order in which the nodes are visited in an in-order traversal. [1]

(d) The tree is a binary search tree. Explain how your answer to part (b) shows this. [2]

(a) 40, 25, 15, 32, 60, 50, 75(1)
(b) 15, 25, 32, 40, 50, 60, 75(1)
(c) 15, 32, 25, 50, 75, 60, 40(1)
(d) In-order traversal gives the values in ascending (sorted) order(1)
(d) Because every value in a left subtree is smaller than its parent and every value in the right subtree is larger, visiting left, root, right produces ascending order(1)
Answer: (a) 40, 25, 15, 32, 60, 50, 75 (b) 15, 25, 32, 40, 50, 60, 75 (c) 15, 32, 25, 50, 75, 60, 40 (d) In-order gives sorted order.
Examiner tip: Pre-order is root-left-right, in-order is left-root-right, post-order is left-right-root – say the rule to yourself before you trace.

2Standard4 marks

(a) Convert the infix expression (3 + 4) * (8 - 2) to reverse Polish notation (RPN). [2]

(b) Evaluate the RPN expression 5 1 2 + 4 * + 3 -. Show the contents of the stack as you work. [2]

(a) 3 4 + – the first bracket converted correctly(1)
(a) 3 4 + 8 2 - * – complete expression with * last(1)
(b) Evidence of correct stack use, e.g. 1 and 2 added to give 3, then 3 × 4 = 12 (stack 5, 12)(1)
(b) 5 + 12 = 17, then 17 − 3 = 14(1)
Answer: (a) 3 4 + 8 2 - * (b) 14
Examiner tip: Operands keep their order in RPN; only operators move – and for subtraction the first value popped is the right-hand operand.

Book a free 30-minute session on WhatsApp and we'll find exactly which step is costing you the marks. Or build a timed paper on it.