Loading…
Free A-Level Computer Science guide
Learn the rules for visiting a tree, follow a post-order traversal one subtree at a time, and practise with a diagram beside each question.
Content owner: Michael Print · Written for A-Level learners · Checked against official specifications
Visiting a node means recording its value. You may reach a node and pass through it before its turn to be recorded.
Pre-order: node → left subtree → right subtree. In-order: left subtree → node → right subtree. Post-order: left subtree → right subtree → node. Apply the chosen rule again inside every subtree.
Breadth-first: record the root, then the next level, then the next. In this guide, process each level from left to right.
The root is the starting node. A leaf has no children. A subtree includes a child and every node below it. An empty child link contributes no visits.
OCR H446 explicitly requires post-order and breadth-first traversal. Pre-order and in-order are included to make the different visit points clear. You can work through the diagrams without reading Python.
Start at the root. Whenever a step says to traverse a subtree, repeat that method's entire rule there before continuing. At a leaf, both subtrees are empty, so record the leaf once. At an empty link, return without recording anything.
Node → Left → Right
Record each subtree's root before its descendants.
Left → Node → Right
Record each subtree's root between its two subtrees.
Left → Right → Node
Record each subtree's root after its descendants.
At root 8, wait to record 8: its left and right subtrees must finish first. The same waiting rule applies to node 3, node 6 and every other subtree root.
Post-order: the completed visit sequence
Notice that 6 comes after both 4 and 7, 3 comes after its whole subtree, and 8 comes after every other node. The rule applies at every level.
Record 8 immediately. In its left subtree, record 3 before 1 and the subtree rooted at 6. Then complete the right subtree, starting with 10.
Pre-order
At 3, finish leaf 1, record 3, then finish 6's subtree as 4, 6, 7. Only after that whole left side can you record 8 and traverse its right side.
In-order
This is increasing order because this example is a BST. In-order traversal of an arbitrary binary tree need not be numerically sorted.
Record the root, then all nodes one edge below it, then all nodes two edges below it. Process existing children left before right. A FIFO queue remembers which node has been waiting longest.
After recording 3, node 10 is already waiting ahead of 3's children. That is why 10 is visited before 1 or 6.
| Level from root | Nodes from left to right |
|---|---|
| 0 | 8 |
| 1 | 3, 10 |
| 2 | 1, 6, 14 |
| 3 | 4, 7, 13 |
Breadth-first visit sequence
| Node recorded | Children added at the back | Queue afterwards |
|---|---|---|
| 8 | 3, 10 | [3, 10] |
| 3 | 1, 6 | [10, 1, 6] |
| 10 | 14 | [1, 6, 14] |
| 1 | None | [6, 14] |
| 6 | 4, 7 | [14, 4, 7] |
| 14 | 13 | [4, 7, 13] |
| 4 | None | [7, 13] |
| 7 | None | [13] |
| 13 | None | [] |
A binary tree has at most two children per node. A BST adds a key-ordering rule at every node:
This example keeps unique integers and ignores duplicate insertions. The traversal rules also work on binary trees without this key ordering.
To search for 9, compare with 8 and go right, then compare with 10 and go left. That link is empty, so 9 is absent.
Before 7 was inserted, compare 7 with 8, then 3, then 6: left → right → right. Attach a leaf at 6's empty right link.
Deleting 3 uses its smallest right-subtree key, 4. Replace 3's key with 4, then remove the old 4 leaf by clearing 6's left link. The other descendants remain connected.
| Number of children | What replaces the incoming link |
|---|---|
| 0 | An empty link |
| 1 | The only child |
| 2 | Keep the node; replace its key with the smallest right-subtree key, then remove that successor |
Using the largest left-subtree key is another valid two-child deletion convention.
A BST is not automatically balanced: sorted insertions can create a chain. Let n be the node count and h the tree height.
| Operation | Cost | Why |
|---|---|---|
| Search, insert or delete: balanced BST | O(log n) time | Follow a path of logarithmic height |
| Search, insert or delete: skewed BST | O(n) time | A path can include every node |
| Full traversal | O(n) time | Visit all n nodes |
| Depth-first recursion | O(h) working stack space | Keep the unfinished calls along a path |
| Breadth-first traversal | Up to O(n) queue space | A wide tree can leave many nodes waiting |
Practise on a new tree rooted at 9. Each diagram is supplied with its question, and each question starts from the unchanged tree. Five questions total 19 marks; answers are indicative.
Search the tree below for 7. State the keys compared, link directions and result.
Indicative answer: Compare 9, 4 and 7 in order (1). Follow left, then right (1). The key matches, so the result is true (1).
Give the post-order and breadth-first sequences for the tree below, processing left before right. Explain why a queue supports breadth-first traversal.
Indicative answer
Using the smallest right-subtree key as successor, explain how to delete key 4 from the tree below.
Indicative answer: The successor is 6 (1), the smallest key in 4's right subtree (1). Replace key 4 with 6 (1), then remove the original 6 leaf by clearing 7's left link (1). Preserve the other links.
Insert 2, 4, 6 and 8, in that order, into an initially empty, unbalanced BST. Describe the shape, explain the worst-case search cost for n increasing keys, and say how balancing helps.
Indicative answer: Each larger key becomes the previous node's right child, creating a chain (1). Searching for its last key can visit all n nodes, so worst-case time is O(n) (1). Balancing limits the height to O(log n), supporting logarithmic search (1).
For comparison practice, give this tree's pre-order and in-order sequences. Explain why its in-order sequence is increasing.
Indicative answer
Use this after tracing by hand. The code builds the worked tree rooted at 8, not the practice tree rooted at 9. Recursive post-order calls follow Left → Right → Node; the queue implements level-by-level visiting.
from collections import deque
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(root, value):
if root is None:
return Node(value)
if value < root.value:
root.left = insert(root.left, value)
elif value > root.value:
root.right = insert(root.right, value)
# Equal values are ignored in this example.
return root
def contains(root, target):
while root is not None:
if target == root.value:
return True
root = root.left if target < root.value else root.right
return False
def post_order(root, result):
if root is not None:
post_order(root.left, result)
post_order(root.right, result)
result.append(root.value)
def breadth_first(root):
if root is None:
return []
waiting = deque([root])
result = []
while waiting:
node = waiting.popleft()
result.append(node.value)
if node.left is not None:
waiting.append(node.left)
if node.right is not None:
waiting.append(node.right)
return result
root = None
for value in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
root = insert(root, value)
depth_first = []
post_order(root, depth_first)
print(depth_first) # [1, 4, 7, 6, 3, 13, 14, 10, 8]
print(breadth_first(root)) # [8, 3, 10, 1, 6, 14, 4, 7, 13]
print(contains(root, 7)) # True
print(contains(root, 9)) # FalseAn empty tree produces no visits and a search returns false. Assign the result of insert because it may create a root. The queue removes its oldest node first. Read the Paper 2 foundations for recursion and queue context.
def remove(root, target):
if root is None:
return None
if target < root.value:
root.left = remove(root.left, target)
elif target > root.value:
root.right = remove(root.right, target)
else:
if root.left is None:
return root.right
if root.right is None:
return root.left
# Two children: use the smallest value in the right subtree.
successor = root.right
while successor.left is not None:
successor = successor.left
root.value = successor.value
root.right = remove(root.right, successor.value)
return root
# Run after the first example: root currently contains the nine values.
root = remove(root, 3)
print(breadth_first(root)) # [8, 4, 10, 1, 6, 14, 7, 13]Assign the returned root when deleting: removing the root can change it. A missing key leaves the tree unchanged. Exclude the returned visit list when comparing working stack/queue space.
OCR H446 §2.3.1(e) names depth-first post-order and breadth-first traversal. §1.4.2(b–c) provides structure/manipulation context. Pre-order and in-order here are supporting comparisons. The diagrams, explanations and questions are original teaching material.
These are independently written explanations and practice questions. CompSciTutoring.co.uk is not affiliated with or endorsed by an examination board. The marking guidance is indicative; always check the syllabus for your examination year.
Found an error? Email a correction.
Use the free examples first, then explore one-to-one tuition if guided practice would help.