Understand depth-first and breadth-first graph traversal, the data structures they use, and the pre-order, in-order and post-order tree traversal algorithms.

What this dot point is asking

AQA wants you to describe depth-first and breadth-first traversal of a graph, name the data structure each uses, and apply the pre-order, in-order and post-order traversals of a binary tree.

Graph traversal

A visited list (or marking) is kept in both so that vertices are not processed twice, which matters in graphs with cycles: without it, a cyclic graph would cause an infinite loop. The choice of stack versus queue is exactly what gives each its character: a stack returns the most recently added vertex (so the search dives deep), while a queue returns the oldest (so the search spreads wide before going deeper).

Tree traversal

preOrder(node):  visit(node); preOrder(left); preOrder(right)
inOrder(node):   inOrder(left); visit(node); inOrder(right)
postOrder(node): postOrder(left); postOrder(right); visit(node)

In-order traversal of a binary search tree outputs the values in ascending order, which is a handy way to test whether a tree is a valid BST. Pre-order can copy or serialise a tree because it records the root first, letting the same structure be rebuilt; post-order is used to evaluate an expression tree and to delete a tree safely, because children are processed before the parent.

These three orderings are all forms of depth-first traversal applied to a tree, so they too are naturally recursive: each definition processes a node and then calls itself on the left and right subtrees in a particular order. The recursion uses the call stack, which is the tree analogue of the explicit stack used for depth-first traversal of a general graph. Breadth-first traversal of a tree, by contrast, visits the tree level by level and uses a queue, just as it does on a graph; this level-order traversal is useful when you want the nodes nearest the root first.

The choice of traversal is driven by what you need to do with the nodes. If you must process a parent before its children (for example printing a directory before its contents, or copying a structure top down) you use pre-order. If you need the values in sorted order from a search tree you use in-order. If you must process all children before their parent (for example freeing memory, or evaluating an arithmetic expression where operands must be known before the operator is applied) you use post-order. Being able to justify the choice, not just produce the sequence, is what higher-mark questions reward.