Purple = root | Blue = internal node | Green = leaf node
Binary Search Tree (BST)
A Binary Search Tree is a binary tree with an ordering property:
All values in the LEFT subtree of a node are LESS THAN the node's value
All values in the RIGHT subtree of a node are GREATER THAN the node's value
This property holds for EVERY node in the tree (not just the root)
This ordering enables efficient binary search — at each node, you can determine which subtree to search, halving the search space. Average case: O(log n). Worst case (degenerate/unbalanced tree): O(n).
BST — Insert Algorithm
// Insert value into BST — compare at each node, go left/right PROCEDUREInsertBST(value : INTEGER) IFroot = NULLTHEN root ← NEWnode(value) // empty tree ELSE current ← root WHILETRUE IFvalue < current.dataTHEN IFcurrent.left = NULLTHENcurrent.left ← NEWnode(value) : EXIT WHILE ELSEcurrent ← current.left ELSE IFcurrent.right = NULLTHENcurrent.right ← NEWnode(value) : EXIT WHILE ELSEcurrent ← current.right ENDWHILE ENDIF ENDPROCEDURE
BST Tree Traversals
Three classic traversal methods process every node exactly once:
In-order
Left → Root → Right
Visits all nodes in ascending sorted order. Used to extract sorted data from a BST. For the tree above: 20, 30, 40, 50, 60, 70, 80.
Pre-order
Root → Left → Right
Root visited FIRST before its subtrees. Used to COPY a tree or produce prefix expressions. For the tree above: 50, 30, 20, 40, 70, 60, 80.
Post-order
Left → Right → Root
Root visited LAST after its subtrees. Used to DELETE a tree (leaves before roots) or produce postfix (RPN) expressions. For tree above: 20, 40, 30, 60, 80, 70, 50.
Hash Tables
A hash table is a data structure that maps keys to values using a hash function. The hash function converts the key into an index (position) in an array. This enables near-constant O(1) average-case search, insert, and delete.
23 MOD 7 = 2 | 45 MOD 7 = 3 | 16 MOD 7 = 2 (COLLISION!) | 9 MOD 7 = 2 (COLLISION!)
0
—
1
—
2
23 → (16 and 9 collide here)
3
45
4
16 (linear probe → slot 4)
5
9 (linear probe → slot 5)
6
—
Collisions
A collision occurs when two different keys hash to the same index. Collisions are inevitable in any realistic hash table. Two common resolution strategies:
⛓ Chaining (Open Hashing)
Each slot in the hash table contains a LINKED LIST of all keys that hash to that index. Colliding keys are simply appended to the chain. Easy to implement; table never "fills up". Disadvantage: extra memory for linked list pointers; poor cache performance if chains are long.
🔍 Linear Probing (Open Addressing)
When a collision occurs, look at the NEXT slot (index + 1). If also occupied, try index + 2, etc. (wrapping around if needed). Simple; no extra linked lists. Disadvantage: "clustering" — long runs of occupied slots develop, slowing future searches; table CAN fill up.
Good Hash Functions
A good hash function should be:
Deterministic — same key always produces the same hash
Uniform distribution — spreads keys evenly across the table to minimise collisions
Fast to compute — O(1) calculation
Table size should be prime — using a prime number as the modulo divisor produces better distribution
Hash Table vs BST Comparison
Feature
Hash Table
BST
Average search
O(1)
O(log n)
Worst case search
O(n) — all keys collide
O(n) — unbalanced/degenerate tree
Ordered access
❌ Not ordered
✅ In-order traversal gives sorted output
Memory
Pre-allocated array
Dynamic (only what's needed)
Best for
Fast lookup by exact key
Sorted data, range queries, traversal
Cambridge 9618 exam tip: Know all three traversal orders — in-order (left-root-right, gives sorted order), pre-order (root-left-right, copies tree), post-order (left-right-root, deletes tree). In-order traversal of a BST ALWAYS gives ascending sorted order — examiners frequently test this. For hash tables, know the basic hash function (key MOD tableSize), what a collision is, and both resolution strategies. Explain linear probing by showing the next available slot calculation. Know the terms: perfect hash (no collisions) vs collision (two keys → same index).
⚠️ Common Mistakes
Confusing traversal orders — a common trick is to ask what pre-order gives (root first, then left subtree, then right subtree) vs in-order (left first, then root, then right). Remember: IN-order = sorted order; PRE-order = root FIRST; POST-order = root LAST.
BST property at every node — the BST ordering property (left < node < right) must hold for ALL nodes, not just the root. A value in the left subtree of the root must be less than every ancestor, not just its immediate parent.
O(1) is average case for hash tables — hash tables are NOT always O(1). Worst case (all keys collide) degrades to O(n). Examiners look for this nuance — always say "average O(1)".
Degenerate BST — if keys are inserted in sorted order (e.g. 1, 2, 3, 4, 5), the BST degenerates into a linear linked list with no left children — O(n) search. A balanced BST avoids this. Mention this when comparing BSTs to hash tables.
Modulo arithmetic — remember that key MOD tableSize gives the hash index. If tableSize = 10 and key = 47, index = 47 MOD 10 = 7. If key = "cat" (a string), its character codes must be summed first before applying MOD.
✅ Notes completed!
▶
Video coming soon
Click slide or press arrow keys to navigate
Worksheet — 4.3.3 Trees & Hash Tables
8 questions · Cambridge 9618 standard
Q1The values 40, 25, 60, 15, 35, 50, 70 are inserted (in that order) into an empty BST. Draw the resulting tree and state the BST ordering property.[4]
✅ Mark scheme
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 [1]; Resulting tree: Root=40; 25 goes left of 40 (25<40); 60 goes right of 40 (60>40); 15 goes left of 25 (15<25); 35 goes right of 25 (35>25, 35<40); 50 goes left of 60 (50<60, 50>40); 70 goes right of 60 (70>60) [1 per correctly placed pair, max 3]. Award marks for any correct ASCII/diagram representation showing correct parent-child relationships.
Q2For the BST built from values 50, 30, 70, 20, 40, 60, 80, state the output of: (a) in-order traversal, (b) pre-order traversal, (c) post-order traversal.[3]
✅ Mark scheme
(a) In-order (Left-Root-Right): 20, 30, 40, 50, 60, 70, 80 [1] — note this gives ascending sorted order; (b) Pre-order (Root-Left-Right): 50, 30, 20, 40, 70, 60, 80 [1]; (c) Post-order (Left-Right-Root): 20, 40, 30, 60, 80, 70, 50 [1]. Award 1 per correct complete traversal sequence. Deduct if any values are missing or in wrong order.
Q3Explain what a hash function is and why hash tables enable near-constant O(1) average-case search. Give an example using key MOD tableSize.[4]
✅ Mark scheme
A hash function is a function that converts a key (integer, string, etc.) into an array index (position) in the hash table — it maps the key directly to its storage location [1]; O(1) average search: to find a key, apply the hash function to compute its index, then directly access that array position — this is a single calculation regardless of table size (no searching through elements) [1]; example: tableSize = 7, key = 45; index = 45 MOD 7 = 3; so 45 is stored at (and retrieved from) index 3 in one step [1]; "average" because collisions can occur — if multiple keys hash to the same index, the table must search through the collision chain/probed slots, degrading performance toward O(n) in the worst case [1].
Q4Explain what a collision is in a hash table and describe how linear probing resolves it. State one disadvantage of linear probing.[4]
✅ Mark scheme
Collision: occurs when two different keys produce the same hash value (index) — i.e. both keys hash to the same array slot [1]; linear probing: when a collision occurs, check the NEXT consecutive slot (index + 1); if also occupied, check index + 2, and so on; if the end of the table is reached, wrap around to index 0 — continue until an empty slot is found [1]; linear probing example: keys 23 and 16 both hash to index 2 (table size 7); 23 inserted at 2; 16 probes index 3 (occupied by 45), then index 4 (empty) — stored at 4 [1]; disadvantage: "clustering" — consecutive occupied slots build up in dense regions; future insertions and searches for those keys must probe through the entire cluster, degrading from O(1) toward O(n); the table can also become genuinely full [1].
Q5State one application of each traversal type: in-order, pre-order, post-order. Justify your choice.[3]
✅ Mark scheme
In-order: used to extract sorted data from a BST — in-order traversal of a BST always visits nodes in ascending sorted order; useful for outputting a sorted list [1]; pre-order: used to copy/duplicate a tree — by visiting the root before its children, the cloned tree can be built with the same structure (root must exist before children can be attached) [1]; OR: used by compilers to generate prefix notation expressions [1]; post-order: used to safely delete a tree — by visiting children before their parent, leaf nodes are deleted first and then their parents; deleting a parent before its children would leave orphaned nodes [1]; OR: used to evaluate postfix (RPN/reverse Polish notation) expressions [1]. Award 1 per correctly named application with justification (why that traversal is appropriate).
Q6State two differences between a hash table and a BST for storing and retrieving data. For each, state when you would prefer one over the other.[4]
✅ Mark scheme
Difference 1 — access speed: hash table gives average O(1) search/insert by computing an index directly; BST gives O(log n) average search by navigating the tree; prefer hash table for very fast lookup by exact key (e.g. dictionary/database lookup); prefer BST if O(log n) is acceptable and data structure must support range queries [1][1]; Difference 2 — ordered data: hash table does NOT maintain data in any order — no traversal gives sorted output; BST maintains order — in-order traversal produces sorted output; prefer BST when sorted output, successor/predecessor queries, or range queries are needed; prefer hash table when only exact key lookup is needed and order does not matter [1][1].
Q7A binary search tree (BST) is built by inserting the values 50, 30, 70, 20, 40 in that order. Draw the resulting tree structure by listing each node and its left and right children. Then state the order in which values would be visited during an in-order traversal.[5]
✅ Mark scheme
Root = 50; 50's left = 30, 50's right = 70 [1]; 30's left = 20, 30's right = 40 [1]; 70 is a leaf (no children) [1]; In-order traversal visits left subtree, root, right subtree recursively: 20, 30, 40, 50, 70 [2] (award 1 if correct sequence but minor error).
Q8A hash table of size 7 uses the hash function h(k) = k MOD 7. Keys to insert are: 14, 21, 9, 16. Show where each key is placed. Key 16 causes a collision — describe how chaining resolves this collision and state one advantage and one disadvantage of chaining over open addressing.[5]
✅ Mark scheme
h(14)=0, h(21)=0, h(9)=2, h(16)=2 [1]; 14→slot 0, 9→slot 2 placed first [1]; 21 collides at slot 0 — with chaining, a linked list is maintained at slot 0; 21 is appended to the list at slot 0 [1]; 16 collides at slot 2 — appended to linked list at slot 2 [1]; Advantage: table never becomes full, any number of collisions can be handled [1]; Disadvantage: extra memory for pointers / slower lookups due to traversing the chain (award 1 for either).
Topic Quiz
Question 1 of 10
You scored
out of 10
Card 1 of 8
Click to reveal definition
🎉
All cards reviewed!
Term
Definition
🎯
Mini Test — 4.3.3 Trees & Hash Tables
10 questions · 10 marks · 10 minutes
⏱ 10:00
Section A — Multiple Choice [5 marks]
Q1Which traversal of a Binary Search Tree produces the values in ascending sorted order?
Q2In a Binary Search Tree, where is a new value 45 placed if the current node has value 50?
Q3A hash table has size 11. Key = 73. What is the hash index using key MOD tableSize?
Q4A node in a tree with NO children is called:
Q5Which collision resolution strategy uses a linked list at each hash table index?
Section B — Short Answer [5 marks]
Q6The values 10, 5, 15, 3, 7 are inserted (in order) into an empty BST. Write the result of (a) in-order traversal, (b) pre-order traversal.
Mark schemeTree structure: root=10; 5 left of 10; 15 right of 10; 3 left of 5; 7 right of 5; (a) In-order (Left-Root-Right): 3, 5, 7, 10, 15 [1] — note ascending sorted order; (b) Pre-order (Root-Left-Right): 10, 5, 3, 7, 15 [1]. Deduct if any values missing or wrong order. The in-order output must be ascending (sorted) — 1 mark for recognising this explicitly is a bonus point.
Q7A hash table has size 7. The keys 14, 21, 9, 3 need to be inserted using key MOD 7. Show where each key is stored, identifying any collisions.
Mark scheme14 MOD 7 = 0 → stored at index 0 [1]; 21 MOD 7 = 0 → COLLISION with 14 at index 0; using linear probing: check index 1 (empty) → stored at index 1 [1]; 9 MOD 7 = 2 → stored at index 2 [1]; 3 MOD 7 = 3 → stored at index 3 [1]. Award 1 per correct calculation. If chaining is used instead of linear probing: 14 and 21 both in chain at index 0 — also accept for full marks with correct explanation of which method used.
Q8Explain what is meant by a "degenerate" BST and the impact on search performance.
Mark schemeA degenerate BST occurs when all nodes are inserted in sorted or reverse-sorted order — each new node is always the right child (or always the left child) of the previous node [1]; this creates a tree that degenerates into a linear structure resembling a linked list — every node has only one child [1]; search performance degrades from O(log n) (balanced tree) to O(n) (linear scan) — to find a value, up to n comparisons may be needed; this eliminates the O(log n) advantage of BSTs [1]. Example: inserting 1, 2, 3, 4, 5 in order produces a completely right-leaning tree of height 5 — all nodes in a single chain.
Q9Describe two properties of a good hash function.
Mark schemeProperty 1: Deterministic — the same key must ALWAYS produce the same hash index; a function that gives different results for the same input would be useless (can't find stored items) [1]; Property 2: Uniform distribution — the function should spread keys evenly across all table indices; poor distribution causes clustering (many collisions in one region, empty slots in another), degrading performance [1]; Additional properties (either accepted): fast to compute (ideally O(1)); avalanche effect (small change in key produces very different hash); table size should be prime to improve distribution quality when using MOD [1 bonus].
Q10Post-order traversal visits nodes left-right-root. Explain why this order is used for deleting a tree, and give one other application.
Mark schemePost-order visits children BEFORE their parent — this is essential for deletion because if a parent is deleted before its children, the children become orphaned nodes (unreachable) causing a memory leak [1]; by deleting leaves (childless nodes) first, then their parents, every node is deleted cleanly with no orphans created [1]; other application: evaluating postfix (Reverse Polish Notation) expressions — operands (leaves) are processed before operators (internal nodes); the result of child sub-expressions feeds into the parent operator naturally in post-order [1].