Tree Traversal and Dijkstra's Algorithm | OCR H446

Learning Objectives

By the end of this topic you will be able to:

Apply pre-order, in-order and post-order tree traversal and state the output sequence

Explain Dijkstra's shortest path algorithm step by step

Trace Dijkstra's algorithm on a weighted graph and identify shortest paths

State the time complexity of Dijkstra's algorithm and identify its limitations

Tree Traversal

Tree Traversal Orders

Binary tree (nodes shown as root → left → right):
        5
    3     8
2  4  7  9

Pre-Order: Root → Left → Right

Visit root FIRST, then traverse left subtree, then right subtree.
Output: 5, 3, 2, 4, 8, 7, 9
Use: copying a tree; expression trees in prefix notation

In-Order: Left → Root → Right

Traverse left subtree, then visit root, then right subtree.
Output: 2, 3, 4, 5, 7, 8, 9
Use: binary search trees output sorted order!

Post-Order Traversal

Post-Order and Application

Post-Order: Left → Right → Root

Traverse left subtree, then right subtree, then visit root LAST.
Output: 2, 4, 3, 7, 9, 8, 5
Use: evaluating expression trees (evaluate children before parent); deleting a tree (delete children before parent — safe deletion order)

All three traversals visit every node exactly once — O(n) time complexity, O(h) space where h is the height of the tree (recursion call stack depth). For a balanced tree h = O(log n); for a degenerate (linear) tree h = O(n).

Mnemonic: "Pre" = root is first; "In" = root is in the middle; "Post" = root is last. Always Left before Right in all three orders.

Dijkstra's Algorithm

Dijkstra's Shortest Path

Dijkstra's algorithm finds the shortest path from a single source node to all other nodes in a weighted graph with non-negative edge weights. It is a greedy algorithm — at each step it processes the unvisited node with the smallest known distance.

Steps

1. Assign distance 0 to source; ∞ to all other nodes
2. Add all nodes to an unvisited set
3. Select the unvisited node with the smallest distance (current node)
4. For each neighbour: if distance to current + edge weight < neighbour's current distance, update it (relaxation)
5. Mark current node as visited; remove from unvisited set
6. Repeat from step 3 until destination reached or all nodes visited

Dijkstra's Trace

Tracing Dijkstra's from A

Graph: A–B(4), A–C(2), B–C(1), B–D(5), C–D(8), C–E(10), D–E(2)

Step	A	B	C	D	E	Current
Start	0	∞	∞	∞	∞	A
1	0✓	4	2	∞	∞	C(2)
2	0✓	3	2✓	10	12	B(3)
3	0✓	3✓	2✓	8	12	D(8)
4	0✓	3✓	2✓	8✓	10	E(10)

Shortest paths from A: B=3, C=2, D=8, E=10. Route to E: A→C→B→D→E

Dijkstra's Properties

Complexity and Limitations

Time complexity: O(V²) with a simple array; O((V+E) log V) with a priority queue (min-heap). For dense graphs (many edges), the array version is comparable; for sparse graphs, the priority queue version is significantly faster.

Limitation — negative edges: Dijkstra's algorithm does NOT work correctly with negative edge weights. The greedy assumption (once a node's distance is finalised, it's optimal) breaks down when negative weights allow a later, seemingly longer path to produce a shorter overall distance. Use Bellman-Ford for negative weights.

Single-source only: Dijkstra's finds shortest paths from ONE source to all other nodes. For all-pairs shortest paths, use Floyd-Warshall (O(V³)).

Exam Practice

OCR H446 Style · 5 marks

Apply Dijkstra's algorithm to find the shortest path from S to T in the graph: S–A(3), S–B(6), A–B(2), A–C(5), B–C(1), C–T(4). Show the distance table and the shortest path with total cost.

[5 marks]

Start: S=0, A=∞, B=∞, C=∞, T=∞
Process S: A=3, B=6 → current=A(3)
Process A: B=min(6,3+2)=5, C=3+5=8 → current=B(5)
Process B: C=min(8,5+1)=6 → current=C(6)
Process C: T=6+4=10 → current=T(10)
Shortest path: S→A→B→C→T, total cost = 10

Must correctly show relaxation (updating distances when a shorter path is found) and visit nodes in ascending distance order.

Common Mistakes

Don't Lose Marks

Not updating distances correctly — "relaxation" means: if dist[current] + weight(edge) < dist[neighbour], update dist[neighbour]. Students often forget to check against the current best distance and just overwrite with the new path. Always compare with the existing distance and only update if the new path is shorter.

Confusing in-order with pre-order for BSTs — in-order traversal of a binary search tree produces a sorted (ascending) sequence. Pre-order produces a prefix sequence. OCR exam questions on tree traversal frequently ask for the output sequence — memorise which order produces sorted output (in-order).

Saying Dijkstra's works with negative weights — it does not. This is a very common mistake. If a question mentions negative edge weights, you must state that Dijkstra's algorithm cannot guarantee the correct result and that Bellman-Ford should be used instead.

Tree Traversaland Dijkstra'sAlgorithm