OCR A-Level Computer Science Algorithms and programming (02), June 2025: Question 7

Mark scheme

Show the mark scheme

Question Answer Mark Guidance

7 (a) 1 mark for 2 correctly inserted 3 It must be clear

2 marks for 4 correctly inserted whether a value is a

3 marks for all 5 correctly inserted left or right child of the

parent i.e. do not

50 accept vertical lines

16 55

8 45 51 75

5 20 47 53 60 88

30 57 90

7 (b) 1 mark each to max 2 e.g. 2

• Takes longer to search for a value

• Takes O(n) steps in worst case compared to O(log n) for a balanced tree

• More iterations are required / more depth levels to process

7 (c) 1 mark for starting with correct value on each traversal (max 2) 4

1 mark for full correct traversal (max 2)

Depth: 20 80 75 35 220 450 602 600 402 100

Breadth: 100 35 402 20 75 220 600 80 450 602

How to answer it

Binary Search Trees: Insertion, Balance & Traversals

📋 What This Question Tests

This question evaluates your foundational knowledge of Tree Data Structures (Specification 2.2.1 & 2.3.1):

Node Insertion: Applying binary search tree rules ( left < root < right ) sequentially to place new nodes.
Tree Balance & Efficiency: Explaining Big-O time complexity consequences when a tree degrades into an unbalanced or linked-list-like structure.
Tree Traversals: Executing depth-first traversals (specifically post-order: Left, Right, Root) and breadth-first (level-by-level) traversals accurately.

Part (a) — 3 Marks

Inserting Items into an Ordered Binary Search Tree

Data to insert in order: 5, 30, 53, 57, 90

✅ Correct Tree Placements

Each value must be compared starting from the root node ( 50 ):

5: 50 → 16 → 8 → place as left child of 8.
30: 50 → 16 → 45 → 20 → place as right child of 20.
53: 50 → 55 → 51 → place as right child of 51.
57: 50 → 55 → 75 → 60 → place as left child of 60.
90: 50 → 55 → 75 → 88 → place as right child of 88.

🧠 Exam Technique & Examiner Note

Angle your lines clearly: The mark scheme explicitly states: "It must be clear whether a value is a left or right child of the parent i.e. do not accept vertical lines." Slant lines visibly left or right.
Follow order strictly: If values conflict along the same path, their insertion order dictates who becomes parent and child.

❌ Common Errors

Drawing vertical drop lines: Connecting a node straight down directly under its parent gets penalised because examiners cannot tell if you intended it to be a left or right child.
Placing 57 as right child of 60: Remember that 57 < 60 , so it must branch left from 60.

Mark Allocation:
• 1 mark for 2 correctly placed nodes
• 2 marks for 4 correctly placed nodes
• 3 marks for all 5 correctly placed nodes

Part (b) — 2 Marks

Drawback of an Unbalanced Binary Search Tree

Impact on Search Performance & Time Complexity

✅ Model Answers (Any 2 for 2 marks)

Takes longer to search for a value.
Search complexity degrades to O(n) in the worst case (compared to O(log n) for a balanced tree).
More iterations / comparisons are required because there are more depth levels to traverse.
Effectively degrades into a linear search / linked list structure.

💡 Key Knowledge: Big-O Comparison

Balanced BST: Each comparison eliminates roughly half of the remaining nodes: O(log n).
Completely Unbalanced: Every node has only one child; you must visit all nodes one by one: O(n).

❌ Common Traps

Vague statements: Saying simply "it is inefficient" or "it takes a lot of memory" gains zero marks. You must specify that it takes longer to search or reference the increased number of comparisons/levels.
Confusing Big-O: Top candidates specifically contrast O(n) with O(log n) to secure full marks easily.

Mark Allocation: 1 mark per valid point up to a maximum of 2 marks.

Part (c) — 4 Marks

Tree Traversals: Post-Order vs Breadth-First

Target Tree Root: 100

✅ Correct Traversal Outputs

Depth-first (post-order):

20, 80, 75, 35, 220, 450, 602, 600, 402, 100

Breadth-first:

100, 35, 402, 20, 75, 220, 600, 80, 450, 602

💡 How Each Traversal Works

Post-Order Traversal Rule:

Left Subtree → Right Subtree → Root

Left subtree of 100: Left child is 20. Right branch has 75 with child 80 → visits 20, 80, 75, 35 .
Right subtree of 100: Visits 220, then right subtree of 600 ( 450, 602, 600 ), then 402 .
Root node ( 100 ) is visited last.

Breadth-First Rule:

Level-by-Level (Top to Bottom, Left to Right)

Level 0: 100
Level 1: 35, 402
Level 2: 20, 75, 220, 600
Level 3: 80, 450, 602

📐 Traversal Shortcut: "The Outline Method"

Pre-order: Place a dot on the left of each node. Trace around the perimeter from the top-left; record the node when you pass its dot.
In-order: Place a dot on the bottom of each node.
Post-order: Place a dot on the right of each node. Trace counter-clockwise around the whole tree; output the node only when your pen crosses the dot on its right!

❌ Common Traversal Mistakes

Mixing up In-order and Post-order: In-order gives values in sorted numerical order. Post-order visits both children before their parent.
Missing nodes in Breadth-first: Ensure you read strictly from left to right along each tier before dropping to the next depth tier.

Mark Allocation:
• 1 mark for starting depth-first with 20; 1 mark for full correct sequence.
• 1 mark for starting breadth-first with 100; 1 mark for full correct sequence.

Topics

1.4 Data types, data structures and algorithms · 2.3 Algorithms · 1.4.2 Data Structures · 2.3.1 Algorithms