SLIDE 1 / 10
CSZone.co.uk
Click anywhere to advance · Arrow keys also work
AQA 7517 · Paper 1 · 4.3.2

Tree
Traversal

Pre-order · In-order · Post-order · Section 4.3 Algorithms

WHAT YOU'LL LEARN
3 recursive traversal methods · When to use each · BST in-order = sorted · AQA exam outputs
AQA SPEC LINK
4.3.2 — Tree traversal algorithms
The Test Tree

Example Binary Tree

We will use this BST for all three traversals:
        F
      /     \
    B       G
   /  \       \
  A   D      I
      /  \    /
     C  E  H
Pre-order Traversal

Pre-order: Root → Left → Right

Visit the root first, then recursively traverse left subtree, then right subtree.
PROCEDURE preOrder(node)
  IF node ≠ null THEN
    OUTPUT node.data
    preOrder(node.left)
    preOrder(node.right)
  ENDIF
ENDPROCEDURE
Result: F B A D C E G I H
Use: copying a tree structure, creating prefix (Polish) notation
In-order Traversal

In-order: Left → Root → Right

Traverse left subtree first, then visit root, then right subtree.
PROCEDURE inOrder(node)
  IF node ≠ null THEN
    inOrder(node.left)
    OUTPUT node.data
    inOrder(node.right)
  ENDIF
ENDPROCEDURE
Result: A B C D E F G H I
KEY FACT: In-order traversal of a BST always gives nodes in sorted order
Post-order Traversal

Post-order: Left → Right → Root

Traverse left subtree, then right subtree, then visit root last.
PROCEDURE postOrder(node)
  IF node ≠ null THEN
    postOrder(node.left)
    postOrder(node.right)
    OUTPUT node.data
  ENDIF
ENDPROCEDURE
Result: A C E D B H I G F
Use: deleting a tree safely, generating postfix (Reverse Polish) notation
Results Summary

All Three Traversals on Same Tree

PRE-ORDER (RLR)
F B A D C E G I H
IN-ORDER (LRL)
A B C D E F G H I
POST-ORDER (LRR)
A C E D B H I G F
Memory aid: position of ROOT in the visit order = Pre (1st), In (2nd), Post (3rd).
Applications

When to Use Each Traversal

Pre-order — copying/cloning a tree; generating prefix notation expressions
In-order — outputting BST values in sorted order; searching a BST
Post-order — safely deleting a tree (children before parent); generating RPN/postfix
BST in-order = Sorted

Why In-order Gives Sorted Output

A BST has the property: left subtree values < parent < right subtree values. In-order visits left before root before right — so it naturally outputs smallest to largest.
This means BST + in-order traversal = an efficient way to sort data. Insert all values → in-order traverse → sorted output.
AQA Exam Style

Practice Question

AQA 7517 — Paper 1 Style
A binary tree has the following structure:
Root: 8 · Left child: 3 (left: 1, right: 6) · Right child: 10 (right: 14)
(a) Write the output of an in-order traversal. [2]
(b) Write the output of a post-order traversal. [2]
(c) Give ONE use of in-order traversal on a BST. [1]
[5 marks]
2 marks
(a) 1, 3, 6, 8, 10, 14 (in-order: left→root→right at every level)
2 marks
(b) 1, 6, 3, 14, 10, 8 (post-order: left→right→root)
1 mark
(c) Outputs values in ascending (sorted) order
Summary

Key Points to Remember

Pre-order: Root, Left, Right — use for copying trees
In-order: Left, Root, Right — use for sorted BST output
Post-order: Left, Right, Root — use for safe deletion & RPN
All three are recursive — each subtree uses same method
BST in-order = ascending sorted order (guaranteed by BST property)
🎉 Lesson complete — move to the quiz!