Skip to topic
    ← Back to course topics

    Simple tree-traversal algorithms — AQA A-Level Computer Science

    Simple tree-traversal algorithms systematically visit every node in a binary tree structure using pre-order, in-order, or post-order depth-first approaches. In AQA A-Level Computer Science, mastering these recursive traversals is vital for evaluating expressions, searching binary search trees, and producing linear serialisations of hierarchical data.

    Simple tree-traversal algorithms explained

    Tracing a tree-traversal algorithm means following its steps on a given binary tree and recording the order in which nodes are visited.

    Read the full explanation

    Start at the root, apply the rule for the chosen traversal to each subtree recursively, and write each node's value as it is visited. Tracing requires you to know the visiting order that each algorithm uses, not merely its name, so practise by drawing a small tree with labelled nodes, then working through the recursive calls one at a time. Keep a running list of output values and check that every node appears exactly once. This skill is tested by asking for the output sequence from a given tree, so accuracy depends on careful, systematic tracking rather than guessing from the tree's shape.

    Your focus

    1. Be able to trace the tree-traversal algorithms:

    Which command word is this?

    Give the exact sequence of nodes or letters without working out or explanation required.

    Simple tree-traversal algorithms exam tips

    Topic Overview

    Tree traversal is the process of visiting every node in a tree data structure exactly once in a defined, deterministic sequence. In AQA A-Level Computer Science, students focus on binary trees and depth-first traversal techniques: pre-order, in-order, and post-order traversals.

    Understanding these traversals is fundamental to processing abstract data types, compilers, and file directory systems. Traversals provide practical ways to linearise hierarchical tree data, enabling tasks such as sorting, tree copying, and the evaluation of arithmetic expression trees without brackets.

    Key Concepts
    • →Pre-order Traversal (Root, Left, Right): Node is visited before its subtrees; commonly used to clone, serialise, or duplicate a tree structure.
    • →In-order Traversal (Left, Root, Right): Left subtree is traversed, then node visited, then right subtree; outputs keys of a Binary Search Tree (BST) in ascending alphanumeric order.
    • →Post-order Traversal (Left, Right, Root): Subtrees are traversed completely before the parent node is visited; used for bottom-up operations like node deletion and producing Reverse Polish Notation (RPN).
    • →Recursive Nature of Trees: Because every subtree is itself a binary tree, traversals are naturally implemented using recursive functions relying on the system call stack.
    Marking Points
    • Starts at the root node of the tree and applies the traversal rule to it first
    • Applies the same rule recursively to each subtree rather than only to the top level
    • Records each node's value at the point the algorithm specifies, producing a complete output sequence
    • Visits every node exactly once and does not omit leaf nodes
    • Produces the output in the order the chosen algorithm dictates for the given tree
    Examiner Tips
    • 💡Write the traversal rule as a three-step pattern before tracing, to keep the order clear
    • 💡Track the output list in a separate column so you can check it against the tree at the end
    • 💡Check that the number of values in your output equals the number of nodes in the tree
    • 💡Use the 'contour' or 'perimeter tracing' method on the exam paper. Draw a tight outline around the tree and drop flags on the left (pre-order), bottom (in-order), or right (post-order) of each node to verify your written sequence.
    • 💡When asked to write pseudo-code for a traversal algorithm, verify your base case first. Forgetting to handle a null or empty pointer loses structural marks.
    Common Mistakes
    • Confuses the visiting order of the three depth-first traversals; learn the position of the root relative to the subtrees for each one
    • Outputs nodes as they are encountered in a left-to-right reading of the diagram; follow the algorithm's rule, not the layout
    • Stops recursion at the first leaf and misses sibling subtrees; continue processing every remaining branch
    • Assuming in-order traversal always produces sorted output for any binary tree: It only outputs sorted data if the tree is strictly a Binary Search Tree (BST).
    • Confusing post-order traversal with reverse in-order traversal: Post-order processes both subtrees before the root (Left, Right, Root), whereas reverse in-order visits Right, Root, Left.
    • Believing tree traversal requires an iterative loop by default: While iterative traversals are possible using explicit stacks, standard AQA A-Level mark schemes expect clear recursive definitions.
    Revision Plan
    1. 1Day 1-2: Review tree terminology and practice manually tracing pre-order, in-order, and post-order paths on small binary trees using the contour method.
    2. 2Day 3-4: Write and trace recursive pseudo-code for all three traversals, noting how the placement of the 'print/visit' statement changes the order.
    3. 3Day 5-6: Study the practical applications of each traversal, specifically expression trees (prefix, infix, postfix) and BST sorting.
    4. 4Day 7: Complete past AQA exam questions under timed conditions to refine accuracy and speed.
    Exam Question Types
    • 📋Tracing output: Given an image of a binary tree, list the exact output sequence for a specified traversal method.
    • 📋Pseudo-code completion: Writing or filling in missing lines of a recursive algorithm implementing pre-order, in-order, or post-order traversal.
    • 📋Expression tree conversion: Converting an infix mathematical expression into a binary tree and stating its postfix form via post-order traversal.
    Command Word Expectations (AQA)
    State

    Give the exact sequence of nodes or letters without working out or explanation required.

    Explain

    Provide clear reasoning detailing why a traversal produces a specific output or how a recursive step functions.

    Write an algorithm

    Provide structured pseudo-code or program code that uses correct recursive calls, parameters, and terminating base conditions.

    How Students Lose Marks (Examiner Pitfalls)
    Pitfall: Confusing the order of visiting the root node relative to its subtrees, especially mixing up post-order with reverse-order traversal.
    ❌ Weak Answer (Loses Marks):Post-order traversal visits the left subtree, then the root, and finishes with the right subtree.
    Example improved answer:Post-order traversal recursively visits the left subtree first, followed by the right subtree, and finally visits the root node (Left, Right, Root).
    Examiner Tip: Draw an outline trace around the perimeter of the binary tree. For pre-order, mark a dot to the left of each node; for in-order, mark underneath; for post-order, mark to the right. Follow the perimeter counter-clockwise to read the nodes in sequence without error.
    Pitfall: Failing to express tree traversals as recursive algorithms or neglecting the base case in pseudo-code questions.
    ❌ Weak Answer (Loses Marks):The algorithm visits a node, then calls traversal on left, then calls traversal on right without checking if the pointer is null.
    Example improved answer:A correct recursive traversal checks if the current node pointer is null (base case). If not null, it processes the current node value and recursively calls the traversal function on the left pointer, then on the right pointer.
    Examiner Tip: In AQA pseudo-code questions, always write the termination condition explicitly: 'IF node != null THEN' before recursive calls to avoid infinite loops and secure full algorithm marks.
    Step-by-Step Worked Solutions

    Question: A binary search tree contains the following values inserted in this order: [50, 30, 70, 20, 40, 60, 80]. Construct the tree and state the sequence of nodes produced by: (a) In-order traversal, (b) Pre-order traversal, and (c) Post-order traversal.

    1. 1.Step 1: Construct the binary search tree. 50 is the root. 30 goes left (< 50), 70 goes right (> 50). 20 goes left of 30, 40 goes right of 30. 60 goes left of 70, 80 goes right of 70.
    2. 2.Step 2: Determine In-order (Left, Root, Right). Leftmost branch first: 20, then root 30, then right 40. Return to main root 50. Process right subtree: left 60, root 70, right 80. Sequence: 20, 30, 40, 50, 60, 70, 80 (ascending sorted order).
    3. 3.Step 3: Determine Pre-order (Root, Left, Right). Visit root 50. Left subtree root 30, then left 20, then right 40. Right subtree root 70, then left 60, then right 80. Sequence: 50, 30, 20, 40, 70, 60, 80.
    4. 4.Step 4: Determine Post-order (Left, Right, Root). Left subtree yields 20, 40, 30. Right subtree yields 60, 80, 70. Finally visit main root 50. Sequence: 20, 40, 30, 60, 80, 70, 50.
    Final Answer: (a) In-order: 20, 30, 40, 50, 60, 70, 80. (b) Pre-order: 50, 30, 20, 40, 70, 60, 80. (c) Post-order: 20, 40, 30, 60, 80, 70, 50.

    Question: An arithmetic expression tree has root operator '+'. The left subtree consists of operator '*' with operands '4' and '5'. The right subtree consists of operator '-' with operands '10' and '2'. Write out the post-order traversal and explain its practical application in computer systems.

    1. 1.Step 1: Identify tree structure. Root: '+'. Left child: '*', which has left child '4' and right child '5'. Right child: '-', which has left child '10' and right child '2'.
    2. 2.Step 2: Apply post-order traversal (Left, Right, Root). Left child subtree: '4', '5', '*'. Right child subtree: '10', '2', '-'. Main root: '+'. Resulting sequence: 4 5 * 10 2 - +.
    3. 3.Step 3: Explain practical application. The output represents Reverse Polish Notation (RPN) or postfix notation. This allows expressions to be evaluated without parentheses using a stack, commonly used in compiler design and stack-based virtual machines (like bytecode interpreters).
    Final Answer: Sequence: 4, 5, *, 10, 2, -, +. Practical application: Generates Reverse Polish Notation (postfix notation) which eliminates ambiguity and parenthesis handling during compiler expression evaluation using an evaluation stack.
    Active Recall Memory Test
    What is the order of node visits in a pre-order traversal?
    Key Fact: Root, Left subtree, Right subtree.
    Which traversal of a Binary Search Tree (BST) outputs keys in ascending numerical order?
    Key Fact: In-order traversal (Left, Root, Right).
    What data notation is generated when performing a post-order traversal on an arithmetic expression tree?
    Key Fact: Reverse Polish Notation (RPN) or postfix notation.
    What is the base case in a recursive tree traversal algorithm?
    Key Fact: Checking whether the current node pointer is null (empty).
    Frequently Asked Questions
    What is the difference between pre-order, in-order, and post-order traversal?
    The difference lies in when the root node is visited relative to its left and right subtrees. Pre-order visits the root first (Root, Left, Right), in-order visits the root between the subtrees (Left, Root, Right), and post-order visits the root after both subtrees (Left, Right, Root). All three are depth-first approaches but serve distinct functional purposes.
    Why does an in-order traversal of a binary search tree produce sorted data?
    By definition, a binary search tree stores all values smaller than the root in the left subtree and all values greater than the root in the right subtree. Because in-order traversal visits all smaller nodes (Left) first, then the current node (Root), and finally all larger nodes (Right), it systematically traverses keys from lowest to highest value.
    How do you trace tree traversals quickly during an exam?
    The most reliable technique is drawing a perimeter line around the entire tree, starting at the root and moving counter-clockwise around every branch. Put a dot on the left of each node for pre-order, on the bottom for in-order, and on the right for post-order. As your perimeter line passes a dot, write down that node's identifier.
    What is tree traversal used for in real-world software?
    Tree traversals are used extensively in compiler design to parse and evaluate mathematical code through abstract syntax trees. They are also used in operating system file managers to calculate the total size of directories, in databases to maintain indexed search trees, and in game development to serialize game-state hierarchies.
    Can tree traversal be done without recursion?
    Yes, tree traversal can be implemented iteratively using an explicit stack data structure to keep track of nodes waiting to be processed. However, recursion is favored in most educational contexts and AQA specifications because it elegantly mirrors the recursive definition of tree structures and uses the system call stack automatically.