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.
See how examiners mark answers
Access past paper questions with model answers. Learn exactly what earns marks and what doesn't.
Search
Insert
Delete
In-order traversal
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 mark-by-mark plan — for / against / judgement, with marking guidance — in study mode.