Mission 1 · Spec 4.3.1 – 4.3.2
Graph and tree traversal
Breadth-first and depth-first graph traversal, and pre-order, in-order and post-order tree traversal, with their typical uses.
- Starter 5 min
- Learn 15 min
- Lab 20 min
- Quiz 10 min
- Exam 15 min
Exploring a building
To search a building for a friend, would you check every room on each floor before moving up, or follow one corridor as far as it goes first?
Reveal
Floor by floor is breadth-first (a queue). One corridor at a time, backtracking at dead ends, is depth-first (a stack).
Key ideas
Breadth-first
Uses a queue. Visits all neighbours before moving further away. Typical use: finding the shortest path in an unweighted graph.
Depth-first
Uses a stack (or recursion). Goes as deep as possible, then backtracks. Typical use: navigating a maze.
Tree traversals
Pre-order (node, left, right): copying a tree. In-order (left, node, right): outputs a binary search tree in order. Post-order (left, right, node): converting infix to RPN, emptying a tree.
Graph traversal
Tree traversal
Exam-style questions
1. State a typical application of breadth-first search and of depth-first search.
[2 marks]Mark scheme
- Breadth-first: shortest path in an unweighted graph (1)
- Depth-first: navigating a maze / finding a path / detecting cycles (1)
2. Explain why a post-order traversal of an expression tree produces reverse Polish notation.
[2 marks]Mark scheme
- Operands are leaves and operators are internal nodes (1)
- Post-order outputs both operands (subtrees) before their operator, which is RPN order (1)
TUTOR NOTES
- Exam habit: AQA asks for traversal outputs from diagrams; practise with the BST lab.
Mission 2 · Spec 4.3.3
Reverse Polish notation
Converting between infix and RPN, and evaluating RPN with a stack.
- Starter 5 min
- Learn 10 min
- Lab 20 min
- Quiz 10 min
- Exam 15 min
No brackets allowed
How can you write (3 + 4) × 5 without brackets so it can't be misread?
Reveal
3 4 + 5 ×. In reverse Polish notation the operator comes after its operands, so brackets and precedence rules are unnecessary.
Key ideas
- RPN (postfix) removes the need for brackets and can be evaluated left to right using a stack.
- It is used by interpreters of stack-based languages, e.g. PostScript and bytecode such as the Java Virtual Machine.
- To evaluate: push operands; on an operator, pop two values, apply it, and push the result.
RPN converter and evaluator
Exam-style questions
1. Convert (a + b) * (c − d) to reverse Polish notation.
Mark scheme
a b + c d − *(1)
2. Show the contents of the stack as 6 2 3 + * is evaluated.
Mark scheme
- Push 6, 2, 3 (1)
- + pops 3 and 2, pushes 5: stack 6, 5 (1)
- * pops 5 and 6, pushes 30 (1)
TUTOR NOTES
- Common slip: the order of operands for − and ÷: the first popped value is the right-hand operand.
Mission 3 · Spec 4.3.4 – 4.3.5
Searching and sorting
Linear, binary and binary tree search; bubble sort and merge sort; and their time complexities.
- Starter 5 min
- Learn 15 min
- Lab 20 min
- Quiz 10 min
- Exam 15 min
Guess my number
Guess a number from 1 to 1,000,000 with "higher/lower" hints. How many guesses at most?
Reveal
20: each guess halves the range and 220 ≈ 1,000,000. That's binary search: O(log n).
Algorithms and complexities
| Algorithm | Time complexity | Notes |
|---|---|---|
| Linear search | O(n) | Works on unsorted data |
| Binary search | O(log n) | Data must be sorted |
| Binary tree search | O(log n) | If the tree is balanced |
| Bubble sort | O(n²) | Simple; in place |
| Merge sort | O(n log n) | Divide and conquer; needs extra memory |
Search race
Sort visualiser
Exam-style questions
1. Explain why the time complexity of merge sort is O(n log n).
[3 marks]Mark scheme
- The list is repeatedly halved, giving log n levels (1)
- At each level, merging processes all n items (1)
- so the total work is n × log n (1)
2. Explain why a binary tree search may take O(n) time in the worst case.
[2 marks]Mark scheme
- If data is inserted in sorted order the tree becomes unbalanced / like a linked list (1)
- so every node may need to be checked (1)
TUTOR NOTES
- Lab prompt: add values 10, 20, 30, 40 to an empty BST. What shape results?
Mission 4 · Spec 4.3.6
Dijkstra's shortest path algorithm
How Dijkstra's algorithm finds the shortest path from a start node to every other node in a weighted graph, and where it is used.
- Starter 5 min
- Learn 10 min
- Lab 20 min
- Quiz 10 min
- Exam 15 min
Routing packets
A router needs the lowest-cost route to every other router on the network. How could it work that out?
Reveal
Using Dijkstra's algorithm: repeatedly take the closest unvisited node and update the distances to its neighbours. Routing protocols such as OSPF use it.
The algorithm
- Set the start node's distance to 0 and all others to ∞.
- Choose the unvisited node with the smallest distance and mark it visited.
- For each neighbour, if the distance via this node is shorter, update its distance and previous node.
- Repeat until every node (or the target) has been visited.
- Trace the previous nodes back from the target to find the route.
A priority queue is often used to choose the next node efficiently. Applications: satellite navigation, network routing, social network "degrees of separation".
Dijkstra step by step
Exam-style questions
1. Using the graph in the lab, trace Dijkstra's algorithm from A, showing the distances table after each node is visited.
[6 marks]Mark scheme
- Correct initial values (1)
- Nodes visited in order of smallest distance (1)
- Distances and previous nodes correctly updated (3)
- Correct final route and total (1)
- Check your answer using "Run to the end" in the lab.
2. Explain why Dijkstra's algorithm does not work correctly with negative edge weights.
[2 marks]Mark scheme
- Once a node is visited its distance is treated as final (1)
- A negative edge found later could make a shorter path to an already-visited node, which would be missed (1)
TUTOR NOTES
- Exam habit: AQA often asks for the table; keep columns for distance, previous and visited.