Community resourceWorksheet

OCR H446 2.3.1 Post-order DFS and breadth-first traversal

Part 12 of 16 · H446 2.3.1 · Algorithms

H446 2.3.1 names post-order depth-first and breadth-first traversal specifically, and each is controlled by a different structure: recursion or an explicit stack for one, a queue for the other. This worksheet produces both orders by hand with the queue state written out, then transfers the same algorithms to a graph where repeats become possible.

Students will:

  • produce post-order depth-first and breadth-first orders for a rooted tree
  • name the controlling structure behind each traversal and say why it fits
  • show queue states as a breadth-first traversal proceeds, including an added child
  • implement both traversals, marking discovered nodes when running on a graph
  • compare the memory demands and typical uses of the two traversals

Inside: 5 explanation cells, 1 multiple-choice question, 1 fill-in-the-blanks cell, 2 written answers and 1 Python task. 29 marks, about 25 to 40 minutes.

Series: H446 2.3.1 · Algorithms, part 12 of 16.

Shared by Coding PathwayVerified teacher

  • 10 cells
  • About 30 minutes
  • CC BY-SA 4.0
  • Shared 31 Aug 2026
  • Updated 3 Sept 2026

Preview

The whole resource, exactly as a class sees it. Answers and marking are held back.

Post-order depth-first and breadth-first traversal

Traversal visits every reachable node in a defined order. OCR requires post-order depth-first and breadth-first algorithms.

By the end, you will be able to

  • produce both orders manually;
  • link post-order DFS to recursion/stack and BFS to a queue;
  • read, trace and write both traversals;
  • explain visited-state needs in general graphs.

Reactivate: a tree has no cycles; a general graph may.

Worked model: one tree, two orders

Tree for depth-first post-order and breadth-first traversalABCDEFGpost-order DFS: children before node; BFS: level by level from a queue

For left-to-right children, post-order DFS is D, E, B, F, G, C, A because every child subtree is completed before its parent is output. Record the recursive returns: D returns, E returns, then B; F returns, G returns, then C; finally A.

For BFS, make the queue state visible:

  1. start [A];
  2. visit A, enqueue its children → [B, C];
  3. visit B, enqueue D and E → [C, D, E];
  4. visit C, enqueue F and G → [D, E, F, G];
  5. visit the remaining leaves in FIFO order.

The resulting BFS order is A, B, C, D, E, F, G. The queue is a method, not just a fact to memorise.

Multiple choice1 mark

Which structure controls breadth-first traversal?

  • AStack
  • BHash collision chain
  • CTuple
  • DQueue
Written answer7 marks

Give post-order DFS and BFS orders if node C gains a third child H to the right of G. Show the queue states for BFS.

Use left-to-right child order.

Students type their answer here.

Worked algorithm shapes

Post-order: recursively traverse every child, then output node. BFS: enqueue root; while queue non-empty, dequeue/output node and enqueue children. For a graph, mark discovered nodes so cycles/multiple paths do not repeat forever.

Coding task12 marks
def postorder(node):
    pass

def breadth_first(root):
    pass
Written answer6 marks

Compare memory use and useful applications of post-order DFS and BFS. Include one reason a visited set is necessary on a graph.

Use depth/frontier and dependency/shortest-level examples.

Students type their answer here.

Closed-book checkpoint

Complete each sentence from memory. There is no answer bank and correctness is held for teacher review.

Fill in the blanks3 marks
In completion 1 depth-first traversal, every child subtree is processed before its parent. Breadth-first traversal uses a completion 2 to visit nodes level by level. A general graph also needs a completion 3 set to prevent cycles and repeated processing.

Review your understanding

Before submitting, check that you can explain the central distinction in your own words, expose the intermediate state that supports your answer and apply the method in an unfamiliar context.