Trees & Binary Search Trees: Building & Traversing (OCR A-Level CS 1.4.2)

Free Trees revision resources (OCR A-Level Computer Science, 1.4.2)

We’ve made exam-style practice for this exact topic, free to download: Trees question sheet, mark scheme and cheat sheet. Grab them, have a go, then read the full guide below.

Trees organise data in a hierarchy, and the binary search tree makes searching genuinely fast. Spec points 1.4.2(b) and (c) cover the tree and binary search tree, and how to create, traverse and add to them, including the three traversals examiners test every single year. I'll be honest with you: "draw the BST", "give the pre-order traversal" and "give the in-order traversal" are about as close to guaranteed marks as this paper gets. So let's make them yours.

Let's get the terminology down, build a BST, and master the three traversals.

Tree terminology

A tree is a connected structure with a hierarchy and no cycles. The vocabulary you need:

• Root: the single node at the top.

• Node: an item in the tree; child nodes branch off a parent.

• Leaf: a node with no children.

• Subtree: a node together with all its descendants.

A binary tree is a tree where each node has at most two children (a left child and a right child).

The binary search tree

A binary search tree (BST) is a binary tree with one rule that makes it powerful for searching:

For every node, all values in its left subtree are smaller, and all values in its right subtree are larger.

To insert a value, start at the root and compare: if the new value is smaller, go left; if larger, go right; repeat until you reach an empty spot, and place it there. To search, you do the same comparisons, and at each node you discard half the remaining tree, which is why a balanced BST is fast (similar to a binary search).

Building a BST: a worked example. Insert these names in order: Mango, Cherry, Peach, Apple, Fig, Lemon, Plum.

• Mango is the root.

• Cherry < Mango → left of Mango. Peach > Mango → right of Mango.

• Apple < Mango, < Cherry → left of Cherry. Fig < Mango, > Cherry → right of Cherry.

• Lemon < Mango, > Cherry, > Fig → right of Fig. Plum > Mango, < Peach → left of Peach.

That gives the tree shown above, where each comparison sends the new value left or right until it finds its place.

The three traversals

A traversal visits every node in a set order. The three you must know are defined by when you visit the root relative to its subtrees:

• Pre-order: root, then left subtree, then right subtree (root first).

• In-order: left subtree, then root, then right subtree (root in the middle).

• Post-order: left subtree, then right subtree, then root (root last).

For the tree above:

• Pre-order: Mango, Cherry, Apple, Fig, Lemon, Peach, Plum

• In-order: Apple, Cherry, Fig, Lemon, Mango, Peach, Plum

• Post-order: Apple, Lemon, Fig, Cherry, Plum, Peach, Mango

This is the most important part, and it is a near-guaranteed exam point: an in-order traversal of a BST outputs the values in sorted order, which here means alphabetical. In-order is naturally recursive:

(Pre-order and post-order are the same, just moving the print to before or after the two recursive calls.)

Depth-first vs breadth-first

The three traversals above are all depth-first: they go as deep as possible down one branch before backtracking. The alternative is breadth-first (level-order), which visits all nodes at one level before moving to the next: for our tree, Mango, Cherry, Peach, Apple, Fig, Plum, Lemon. Depth-first is often implemented with a stack (or recursion), breadth-first with a queue.

Why balance matters

If you insert values that are already in order (e.g. Black, Blue, Cyan, Green…), each new value keeps going the same way, so the tree becomes a long thin chain, effectively a linked list. Searching it then degrades to a slow sequential search instead of the fast halving you get from a balanced tree. So the order of insertion affects a BST's performance.

Common exam mistakes

These are the classic slips, and every one of them is easy to avoid once you have seen it.

• Mixing up the three traversals. It's all about when the root is visited: pre = first, in = middle, post = last.

• Forgetting in-order gives sorted output. For a BST, in-order = ascending/alphabetical order.

• Inserting on the wrong side. Smaller goes left, larger goes right: compare at every node from the root down.

• Ignoring balance. Inserting sorted data builds an unbalanced tree that searches as slowly as a list.

• Confusing a tree with a graph. A tree has a root, a hierarchy and no cycles; a general graph need not.

Quick recap

• A tree is a hierarchy with a root, nodes/children, leaves and no cycles; a binary tree has ≤ 2 children per node.

• BST rule: left subtree < node < right subtree; insert/search by comparing and going left or right.

• Pre-order (root first), in-order (root middle), post-order (root last); all are depth-first.

• In-order of a BST = sorted order.

• Breadth-first visits level by level (uses a queue); inserting sorted data makes an unbalanced, slow tree.

The thing that trips people up with trees is rushing. Draw the tree slowly, label the root, and for every value just ask "smaller, go left; larger, go right". Then do the traversals with your finger on the diagram. Get into that habit and trees turn from intimidating into some of the most reliable marks on the paper. I believe in you.

Frequently asked questions

What is a binary search tree? A binary search tree is a binary tree in which, for every node, all values in its left subtree are smaller and all values in its right subtree are larger. This ordering makes searching fast, because each comparison lets you discard half of the remaining tree.

How do you insert a value into a binary search tree? Start at the root and compare the new value with each node: if it is smaller, move to the left child; if it is larger, move to the right child. Repeat until you reach an empty position, and insert the new value there.

What are the three tree traversals? The three depth-first traversals are pre-order (visit the root, then the left subtree, then the right), in-order (left subtree, then root, then right) and post-order (left subtree, then right subtree, then root). They differ only in when the root is visited.

Why does an in-order traversal of a binary search tree give sorted output? Because of the BST ordering rule, the in-order traversal visits the left subtree (smaller values) before the node and the right subtree (larger values) after it. Applying this recursively at every node outputs all the values from smallest to largest.

What is the difference between depth-first and breadth-first traversal? A depth-first traversal goes as deep as possible down one branch before backtracking and is often implemented with a stack or recursion. A breadth-first traversal visits all nodes at one level before moving to the next and is implemented with a queue.

How does the order of insertion affect a binary search tree? If values are inserted in sorted order, each new value goes the same way and the tree becomes a long, unbalanced chain, so searching it is as slow as a linear search. Inserting values in a varied order produces a more balanced tree, which keeps searching fast.