The big idea: In a binary search tree, for every node: everything in its left subtree is smaller, everything in its right subtree is larger.
Not just the two children — every descendant. That is what makes searching work.
Step through: the ordering rule, a search discarding half the tree at each step, an insert, and what sorted input does to it.
Interactive diagram
Explore the labelled diagram, charts and maps for this topic in full study mode.
Free preview
This is the free notes preview
You're reading the free notes. Aimnova Pro unlocks the full study experience — and you can try it with your first topic free to keep:
- FlashcardsLock in vocabulary and key terms with spaced repetition.
- Practice questionsAnswer exam-style questions and get instant AI marking.
- Mock exams & past-paper vaultSit full mocks and see exactly how examiners award marks.
- Personalised study planA daily plan built around your exam date and weak areas.
| Term | Meaning |
|---|---|
| Root | The single node at the top; every path starts here |
| Parent / child | A node and the nodes directly below it — at most two |
| Leaf | A node with no children |
| Subtree | Any node together with everything below it |
| Height | The longest path from root to leaf — what decides the cost |
Height is the whole story: Every operation costs at most the height of the tree, because each step goes down one level and never back up.
A balanced tree of n nodes has height about log₂ n. That is the entire reason a BST is fast.
Asked to sketch a tree after inserting names? Start at the root every time and compare: earlier in the alphabet goes left, later goes right, until there is an empty place.
See how examiners mark answers
Answer exam-style questions with model answers. Learn exactly what earns marks and what doesn't.
Search
Compare with the node. Smaller, go left; larger, go right; equal, found.
Each comparison discards an entire subtree — that is the halving. 1,000 nodes, about 10 comparisons.
Insert
Search for the value. Where the search runs off the end, that gap is where it belongs.
Insertion is a search that ends at an empty child.
Delete
Three cases. A leaf is simply removed. A node with one child is replaced by that child. A node with two children is replaced by its in-order successor — the smallest value in its right subtree.
In-order traversal
Left subtree, then the node, then the right subtree.
This visits every value in sorted order — which is the BST's other party trick.
In-order gives you sorted data free: Because everything left is smaller and everything right is larger, visiting left → node → right produces the values in ascending order with no sorting step at all.
That is often the reason a BST is chosen over a hash table, which has no order whatsoever.
How this is tested — you must apply the ordering rule to search or insert, and explain why the shape of the tree decides the cost. It comes up two ways:
Paper 2 — working with code
- Explain the properties of a BST, 3-4 marks
- Sketch the tree after a list of insertions
- State the result of an in-order traversal
Paper 2 — the algorithmic-thinking question
- Explain why sorted input degrades a BST
- Compare a BST with another structure
The classic trap: Claiming a BST is O(log n) without qualification. It is O(log n) only while balanced — the same values inserted in sorted order give O(n). Say which you mean.
The values 20, 30, 40, 50, 60 are inserted into an empty BST in that order. Explain the shape that results, the cost of searching it, and how a different insertion order would help.
Model answer plan
See the answer broken into clear points, with guidance on how each point earns marks.