Trees and Tree Traversal

AQA 4.2.8 — Trees and traversal

Retrieval: the previous lesson defined a graph as vertices connected by edges. A tree is formally a special, constrained kind of graph: connected, with no cycles, and — for a rooted tree, the kind this course uses — one designated root vertex, with every other vertex reached by exactly one path down from it.

Key vocabulary

• Node — a vertex within a tree (the terms are used interchangeably in this context).
• Root — the single node at the top of the tree, with no parent.
• Parent / child — a node directly above/below another, connected by one edge.
• Leaf — a node with no children.
• Depth (of a node) — the number of edges from the root down to that node.
• Height (of a tree) — the depth of its deepest leaf.
• Binary tree — a tree in which every node has at most two children, conventionally called left and right.

Understand — why trees exist

Many real relationships are naturally hierarchical, not just networked: a file system (folders containing files and other folders), an organisation chart, or a sequence of yes/no decisions. A general graph could model these, but a tree's extra constraints (no cycles, one root, a clear parent–child direction) make hierarchical relationships easier to reason about — and, as this lesson and the next will show, easier to search efficiently too.

See it — a worked binary tree

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

n1 = Node(1)
n4 = Node(4)
n7 = Node(7)
n13 = Node(13)
n6 = Node(6, n4, n7)
n3 = Node(3, n1, n6)
n14 = Node(14, n13, None)
n10 = Node(10, None, n14)
root = Node(8, n3, n10)

This builds a 9-node tree: 8 is the root; 3 and 10 are its children (depth 1); 1, 6, 14 sit at depth 2; 4, 7, 13 at depth 3. The leaves (nodes with no children at all) are 1, 4, 7 and 13.

Understand — the three traversal orders

• Pre-order — visit the node itself, then its left subtree, then its right subtree (root first).
• In-order — visit the left subtree, then the node itself, then the right subtree (root in the middle).
• Post-order — visit the left subtree, then the right subtree, then the node itself (root last).

See it — implementing all three, recursively

def preorder(node):
    if node is None:
        return []
    return [node.value] + preorder(node.left) + preorder(node.right)

def inorder(node):
    if node is None:
        return []
    return inorder(node.left) + [node.value] + inorder(node.right)

def postorder(node):
    if node is None:
        return []
    return postorder(node.left) + postorder(node.right) + [node.value]

Retrieval: the base case — if node is None: return [] — is exactly Sequence 10's recursion pattern applied to a tree instead of a number: recursion needs a case where it genuinely stops, and an empty subtree (a None child) is that case here.

Trace it — in-order, step by step

Tracing inorder(root) on the tree above (each call waits for its recursive calls to return before combining the result, exactly like Sequence 10's stack frames):

Notice the final result is in fully sorted order — not a coincidence for this particular tree, as the next lesson explains.

Debug it — diagnose, explain, fix, test, justify (traversal error)

def inorder(node):
    if node is None:
        return []
    return [node.value] + inorder(node.left) + inorder(node.right)

print(inorder(root))

This runs without crashing at all, but produces [8, 3, 1, 6, 4, 7, 10, 14, 13] — the pre-order sequence, not in-order.

1. Diagnose: compare the position of [node.value] in this version against the definition of in-order (left, node, right).
2. Explain: which of the three traversal orders does placing the value before both recursive calls actually match?
3. Fix: move [node.value] so it sits between the two recursive calls, not before them.
4. Test: confirm the corrected function now returns the fully sorted [1, 3, 4, 6, 7, 8, 10, 13, 14].
5. Justify: explain why this bug is easy to miss without deliberately checking the order of the output — the function still returns a complete, valid-looking list of every value, just in the wrong sequence.

(The value is placed before both recursive calls, which is the pre-order pattern, not in-order. The fix is inorder(node.left) + [node.value] + inorder(node.right). This is dangerous precisely because the function never crashes and never omits a value - only the ORDER is wrong, which a casual glance at "does it return 9 values?" would never catch.)

Common mistake

Confusing a leaf with "any node with only one child." A leaf specifically has zero children; a node with exactly one child is neither a leaf nor "complete" — it's simply an unbalanced branch.

Check your understanding

For the tree built in "See it" above, state the result of a post-order traversal. Explain one genuine situation where post-order traversal is more appropriate than pre-order. (4 marks)

(Post-order: [1, 4, 7, 6, 3, 13, 14, 10, 8]. Post-order is more appropriate when every node's children must be fully processed before the node itself - for example, safely deleting an entire tree from memory, where each node's children must be freed before the node that references them, or evaluating a mathematical expression tree, where both operands must be evaluated before the operator that combines them.)

Challenge

Write a function tree_height(node) that returns the height of a binary tree (the number of edges on the longest path from the root to a leaf), using recursion.

Looking ahead: the next lesson reveals why this particular tree's in-order traversal came out sorted — it satisfies a special extra property called the Binary Search Tree property.