Trees and Binary Trees

This lesson covers trees and binary trees — the first non-linear, hierarchical data structures in the course, in which each node may have several children arranged below it in levels. Trees model anything with a containment or parent–child relationship: file systems, the HTML DOM, decision processes, parsed expressions, and the indexes inside databases. The examinable heart of the topic is precise terminology (root, leaf, edge, subtree, depth, height) and fluent traversal — being able to produce the visiting order for pre-order, in-order, post-order, and breadth-first on any given binary tree.

Spec Mapping

This lesson addresses AQA A-Level Computer Science (7517), section 4.2.7 (Trees), with traversal also drawing on §4.3.2. It covers the definition of a rooted tree, the specialisation to binary trees (at most two children per node), the full vocabulary you are expected to use precisely, the two ways to represent a tree in memory (linked nodes versus an array), and the four standard traversals with their worked output sequences. It builds on §4.2.6 (linked lists — a tree node is a list node with two pointers) and §4.2.3 (queues — used by breadth-first traversal), and leads directly into §4.2.7's binary search tree in the next lesson. All wording below is original; AQA's published specification text is not reproduced.

---

What is a Tree?

A tree is a non-linear, hierarchical structure of nodes joined by edges, satisfying these rules:

• Exactly one node is the root — the single node with no parent, conventionally drawn at the top.
• Every other node has exactly one parent, so there is one unique path from the root to any node.
• A node may have zero or more children.
• There are no cycles — you can never return to a node by following edges downward. (This acyclic, single-parent property is precisely what distinguishes a tree from the more general graph of §4.2.8.)

Key Terminology

You will lose easy marks if these terms are used loosely, so learn them exactly.

Term	Definition
Root	The unique topmost node, with no parent.
Parent	A node that has one or more children directly below it.
Child	A node directly below, and connected to, a parent.
Sibling	Nodes that share the same parent.
Leaf	A node with no children (also called a terminal node).
Internal node	A node with at least one child (a non-leaf).
Edge	A single connection between a parent and one of its children.
Subtree	A node together with all of its descendants, viewed as a tree in its own right.
Path	The sequence of edges from one node to another; in a tree it is unique.
Depth / level	The number of edges from the root down to a node; the root is at depth 0.
Height	The number of edges on the longest path from a node down to a leaf; the height of the tree is the height of its root.
Degree	The number of children a node has.

Example Tree

flowchart TB
    A["A (root, depth 0)"]
    A --> B["B (depth 1)"]
    A --> C["C (depth 1, leaf)"]
    A --> D["D (depth 1)"]
    B --> E["E (depth 2, leaf)"]
    B --> F["F (depth 2, leaf)"]
    D --> G["G (depth 2, leaf)"]

Reading this tree: the root is A; the leaves are C, E, F, and G; B and D are internal nodes; E and F are siblings (shared parent B). Node B has degree 2. The depth of E is 2 (two edges from the root); the height of the whole tree is 2 (the longest root-to-leaf path, e.g. A→B→E). The subtree rooted at B consists of B, E, and F. Distinguishing depth (measured downward from the root) from height (measured upward from the leaves) is a frequent exam discriminator.

---

Binary Trees

A binary tree is a tree in which every node has at most two children, explicitly labelled the left child and the right child. The left/right distinction matters: it is part of the structure, so a node with only a left child is different from one with only a right child.

flowchart TB
    N10((10)) --> N5((5))
    N10 --> N15((15))
    N5 --> N3((3))
    N5 --> N7((7))
    N15 --> N20((20))

Counting Properties of Binary Trees

Because each level can hold at most twice the nodes of the level above, several useful bounds follow. Writing $d$d for depth and $h$h for height:

Property	Formula	Meaning
Maximum nodes at depth $d$d	$2^{d}$2d	level 0 has 1, level 1 has 2, level 2 has 4, …
Maximum total nodes for height $h$h	$2^{h+1} - 1$2h+1−1	a perfect tree of height $h$h
Minimum height for $n$n nodes	$\lfloor \log_2 n \rfloor$⌊log2​n⌋	achieved when the tree is balanced

The last row is the crucial one for performance: if a binary tree of $n$n nodes is kept balanced, its height is only about $\log_2 n$log2​n, so any root-to-leaf operation takes $O(\log n)$O(logn) steps. This is the property the next lesson's binary search tree exploits.

Special Forms of Binary Tree

Type	Description
Full (strict)	Every node has either 0 or 2 children — never exactly one.
Complete	Every level is fully filled except possibly the last, which fills left-to-right. (This is the shape that maps perfectly onto an array.)
Perfect	Every internal node has two children and all leaves are at the same depth.
Balanced	For every node, the heights of its two subtrees differ by at most 1, keeping height $\approx \log_2 n$≈log2​n.
Degenerate (skewed)	Every node has a single child, so the tree collapses into a linked list of height $n-1$n−1.

The contrast between balanced and degenerate is the single most important performance idea about trees: the same $n$n values can form a bushy tree of height $\log_2 n$log2​n or a thin chain of height $n-1$n−1, and every operation's cost follows the height.

---

Representing a Tree in Memory

There are two standard representations, and AQA expects you to know both.

1. Linked Representation (nodes and pointers)

Each node is an object holding its data and two pointers, to its left and right children — a direct extension of the linked-list node from §4.2.6.

class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None     # pointer to left child (or None)
        self.right = None    # pointer to right child (or None)

# Build the example binary tree by linking nodes
root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(7)
root.right.right = TreeNode(20)

This is the dynamic representation: nodes are allocated on the heap as needed, the tree grows and shrinks freely, and there is no wasted space — at the cost of a pointer per child.

2. Array Representation

A complete binary tree can be stored in a plain array with no pointers at all, using index arithmetic. If the root is at index 0, then for the node at index $i$i:

$\text{left child} = 2i + 1, \qquad \text{right child} = 2i + 2, \qquad \text{parent} = \left\lfloor \frac{i-1}{2} \right\rfloor$left child=2i+1,right child=2i+2,parent=⌊2i−1​⌋

So the example tree (read level by level: 10, 5, 15, 3, 7, _, 20) stored at indices 0–6 lets you find any child or parent by calculation:

Index	0	1	2	3	4	5	6
Value	10	5	15	3	7	—	20

The array form is compact and cache-friendly (it is exactly how a binary heap is stored), but it wastes space if the tree is not near-complete: a degenerate tree would need an array of size $2^{n}$2n for $n$n nodes. The trade-off — linked for sparse/irregular trees, array for complete ones — mirrors the static-versus-dynamic theme from §4.2.1.

Worked navigation. Using the array above, take the node at index 1 (value 5). Its left child is at $2(1)+1 = 3$2(1)+1=3 (value 3), its right child at $2(1)+2 = 4$2(1)+2=4 (value 7), and its parent at $\lfloor (1-1)/2 \rfloor = 0$⌊(1−1)/2⌋=0 (value 10) — all confirmed against the drawn tree. Index 5 holds no value because that position (the right child of node 5) is empty in this particular tree, which is why the array representation is only space-efficient when the tree is close to complete: every "gap" still consumes a slot. For a node at index 6 (value 20), the parent is $\lfloor (6-1)/2 \rfloor = \lfloor 2.5 \rfloor = 2$⌊(6−1)/2⌋=⌊2.5⌋=2 (value 15), correctly identifying 20 as the right child of 15. Being able to apply these three formulae both ways — child from parent and parent from child — is a common short-answer exam task.

---

Tree Traversals

Traversal visits every node exactly once in a defined order. The three depth-first traversals differ only in when the root is visited relative to its subtrees, and each is naturally recursive (§4.1.1).

1. Pre-order (Root → Left → Right)

Visit the node first, then recurse left, then right.

def pre_order(node):
    if node is not None:
        print(node.data, end=" ")   # 1) visit root
        pre_order(node.left)        # 2) whole left subtree
        pre_order(node.right)       # 3) whole right subtree

For the example tree the output is 10, 5, 3, 7, 15, 20. Pre-order is used to copy a tree (you create each parent before its children) and to produce prefix (Polish) notation from an expression tree.

2. In-order (Left → Root → Right)

Recurse fully left, then visit the node, then recurse right.

def in_order(node):
    if node is not None:
        in_order(node.left)         # 1) whole left subtree
        print(node.data, end=" ")   # 2) visit root
        in_order(node.right)        # 3) whole right subtree

For the example tree the output is 3, 5, 7, 10, 15, 20. The standout fact: in-order traversal of a binary search tree yields the values in ascending sorted order — the basis of the tree-sort and of range queries in the next lesson.

3. Post-order (Left → Right → Root)

Recurse left, recurse right, then visit the node last.

def post_order(node):
    if node is not None:
        post_order(node.left)       # 1) whole left subtree
        post_order(node.right)      # 2) whole right subtree
        print(node.data, end=" ")   # 3) visit root last

For the example tree the output is 3, 7, 5, 20, 15, 10. Post-order visits every child before its parent, which is exactly what you need to delete/free a tree safely, and to produce postfix (Reverse Polish) notation for evaluation.

Tracing In-order by Hand

The recursion is easiest to trust if you trace it. For the example tree, in-order on the root (10) must finish the entire left subtree (rooted at 5) before printing 10:

Call	Action taken
in_order(10)	go left first → in_order(5)
in_order(5)	go left → in_order(3)
in_order(3)	left is null; print 3; right is null; return
back in in_order(5)	print 5; go right → in_order(7)
in_order(7)	left null; print 7; right null; return
back in in_order(10)	print 10; go right → in_order(15)
in_order(15)	left null; print 15; go right → in_order(20)
in_order(20)	left null; print 20; right null; return

Reading the printed values in order gives 3, 5, 7, 10, 15, 20 — confirming the ascending order and showing exactly how the call stack drives the sequence.

Depth-First Traversal Summary

Traversal	Order	Output for example	Typical use
Pre-order	Root, Left, Right	10, 5, 3, 7, 15, 20	Copy a tree; prefix notation
In-order	Left, Root, Right	3, 5, 7, 10, 15, 20	Sorted output from a BST
Post-order	Left, Right, Root	3, 7, 5, 20, 15, 10	Delete a tree; postfix notation

Exam Tip: Traversal is among the most heavily tested tree skills. Use the mnemonic by where the Root sits: pre = RLR (root first), in = LRR (root middle), post = LRR (root last), and always traverse a whole subtree before moving on.

---

Breadth-First Traversal

Breadth-first (or level-order) traversal visits all nodes at depth 0, then all at depth 1, and so on. Unlike the depth-first traversals it is not naturally recursive — it uses an explicit queue (§4.2.3): dequeue a node, visit it, then enqueue its children, repeating until the queue empties.

from collections import deque

def breadth_first(root):
    if root is None:
        return
    queue = deque([root])           # start with the root
    while queue:
        node = queue.popleft()      # dequeue (FIFO front)
        print(node.data, end=" ")   # visit
        if node.left:
            queue.append(node.left)   # enqueue children for later
        if node.right:
            queue.append(node.right)

Tracing on the example tree, the queue contents (front on the left) evolve: [10] → visit 10, enqueue 5,15 → [5,15] → visit 5, enqueue 3,7 → [15,3,7] → visit 15, enqueue 20 → [3,7,20] → visit 3 → visit 7 → visit 20. Output: 10, 5, 15, 3, 7, 20. The FIFO queue is what guarantees a node's siblings are all visited before its children — the defining contrast with the LIFO stack that drives depth-first search.

Comparing All Four Traversals on One Tree

It is instructive to see all four orders side by side for the example tree (root 10, left subtree 5/3/7, right subtree 15/20), so you can verify each by hand: