Binary Search Trees

A tree is a connected, undirected graph with no cycles. Unlike a general graph, a tree has no loops — there is exactly one path between any two vertices.

A rooted tree is a tree in which one vertex is designated the root. This creates a hierarchy:

• The root has no parent
• Every other node has exactly one parent
• Nodes with no children are called leaves

A binary tree is a rooted tree in which every node has at most two children, referred to as the left child and right child.

A tree does not have to have a root — but a rooted tree does. A binary tree is always rooted.

The most practically important application of a binary tree is the binary search tree (BST). A BST is a binary tree with an ordering property that makes efficient searching possible:

BST ordering property: for every node, all values in its left subtree are less than the node's value, and all values in its right subtree are greater than the node's value.

This property holds at every node in the tree, not just at the root.

Inserting a sequence of values into a BST produces a tree whose structure depends on the order of insertion. Each new value is compared against existing nodes starting at the root and routed left or right until an empty position is found.

Worked example — insert in order: 5, 3, 7, 1, 4, 6, 8

Insert	Action
5	First value — becomes the root
3	3 < 5 → left child of 5
7	7 > 5 → right child of 5
1	1 < 5 → go left → 1 < 3 → left child of 3
4	4 < 5 → go left → 4 > 3 → right child of 3
6	6 > 5 → go right → 6 < 7 → left child of 7
8	8 > 5 → go right → 8 > 7 → right child of 7

Resulting BST:

The ordering property holds at every node: all values in the left subtree of 5 (1, 3, 4) are less than 5; all values in the right subtree (6, 7, 8) are greater. The same applies at each internal node.

Searching a BST uses the ordering property to eliminate half the remaining tree at each comparison — identical in logic to binary search on a sorted array.

Algorithm:

1. Start at the root
2. If the target equals the current node → found
3. If the target is less than the current node → move to left child
4. If the target is greater than the current node → move to right child
5. If the current node is null → target not in tree

Worked trace — search for 4 in the tree above:

Step	Current node	Compare with 4	Decision
1	5	4 < 5	Go left
2	3	4 > 3	Go right
3	4	4 = 4	Found

3 comparisons for a 7-node tree. For a balanced BST with $n$ nodes, the height is approximately ${\log }_{2}n$, giving a time complexity of $O(\log n)$.

Trace — search for 2 (not in tree):

Step	Current node	Compare with 2	Decision
1	5	2 < 5	Go left
2	3	2 < 3	Go left
3	1	2 > 1	Go right
4	null	—	Not found

In-order traversal visits nodes in the order: left subtree → root → right subtree, applied recursively at every node.

InOrder(node):
    IF node IS NOT null:
        InOrder(node.left)
        OUTPUT node.value
        InOrder(node.right)

Trace on the example BST:

In-order visits: 1, 3, 4, 5, 6, 7, 8

Key property of in-order traversal on a BST: it outputs all values in ascending sorted order. This makes in-order traversal the standard algorithm for printing or processing the contents of a BST in sequence.

The reason: the BST ordering property ensures that everything in the left subtree is smaller (visited first), the root is next, and everything in the right subtree is larger (visited last). Applied recursively, this produces a globally sorted sequence.

Use: outputting the contents of a binary search tree in ascending order.

Two other traversal orders are required by the spec. Both use the same recursive approach with the processing step in a different position.

Pre-order: root → left → right

PreOrder(node):
    IF node IS NOT null:
        OUTPUT node.value
        PreOrder(node.left)
        PreOrder(node.right)

Pre-order on the example BST: 5, 3, 1, 4, 7, 6, 8

Pre-order visits the root before its children. This preserves the shape of the tree — a sequence of pre-order values can reconstruct the original BST by inserting them in the same order. Use: copying a tree.

Post-order: left → right → root

PostOrder(node):
    IF node IS NOT null:
        PostOrder(node.left)
        PostOrder(node.right)
        OUTPUT node.value

Post-order on the example BST: 1, 4, 3, 6, 8, 7, 5

Post-order visits a node only after both its children have been processed. Uses: emptying a tree (delete children before parent); evaluating expression trees; converting infix to Reverse Polish Notation (RPN).

Traversal	Order	Primary use
In-order	Left → Root → Right	Output BST contents in ascending order
Pre-order	Root → Left → Right	Copying a tree
Post-order	Left → Right → Root	Emptying a tree; infix to RPN conversion

The time complexity of searching a BST is $O(\log n)$ — but this assumes the tree is reasonably balanced.

A balanced BST with $n$ nodes has height $\approx {\log }_{2}n$. Each comparison eliminates approximately half the remaining nodes, so the number of steps grows logarithmically with the tree size.

Tree size ($n$)	Height (balanced)	Maximum comparisons
7	3	3
15	4	4
31	5	5
1023	10	10

What happens with an unbalanced tree?

If values are inserted in sorted order — e.g., 1, 2, 3, 4, 5 — each new value is always a right child of the previous, producing a tree that is effectively a linked list:

Searching this tree for 5 requires visiting every node. In the worst case (degenerate BST), search time degrades to $O(n)$.

The AQA spec states the time complexity of binary tree search as $O(\log n)$, which holds for a balanced or near-balanced tree. In exam questions, the tree given will typically be balanced unless the question explicitly explores the worst case.

1. Inserting values in the wrong position

When inserting, compare the new value against every node on the path from root to the insertion point, not just the root. Moving left or right at each node is a separate comparison — show all steps in a trace.

2. Confusing the three traversal orders

The orders differ only in when the root is processed relative to its children: in-order (root middle), pre-order (root first), post-order (root last). Learn the mnemonic: in = in the middle, pre = before children, post = after children.

3. Claiming BST search is always $O(\log n)$

$O(\log n)$ is the time complexity for a balanced BST. A degenerate tree (all nodes on one side) degrades to $O(n)$. Exam questions that give a sorted insertion sequence or an obviously unbalanced tree are testing awareness of this.

4. Stating that in-order traversal works for any binary tree

In-order traversal outputs values in ascending order only for a binary search tree — one that satisfies the ordering property. For a general binary tree with no ordering, in-order produces an output, but it will not be sorted.

5. Confusing BST search with binary search

Binary tree search (on a BST) and binary search (on a sorted array) both achieve $O(\log n)$ by repeatedly halving the search space. They are related in concept but different in implementation: one follows pointers in a tree structure; the other uses index arithmetic on an array.