CAIE 9618 · Paper 4 · Topic 4.3.3

Trees &
Hash Tables

Binary Trees · BST Insertion/Search · Pre/In/Post-order · Hash Functions · Collision Handling

CSZone Cambridge International AS & A Level Computer Science 9618

Binary Search Trees

Ordered Tree Structure

BST PROPERTY

For any node: all values in its left subtree are smaller, all values in its right subtree are larger

No duplicate values in a BST

Search O(log n) average — halves search space each comparison

Search O(n) worst case — degenerate tree (all nodes on one side)

TRAVERSALS

Pre-order: Root → Left → Right (copy tree, prefix notation)

In-order: Left → Root → Right (ascending sorted order from BST)

Post-order: Left → Right → Root (delete tree, postfix notation)

Insert: 50, 30, 70, 20, 40 into BST

50

╱╲

3070

╱╲

2040

In-order: 20, 30, 40, 50, 70 (sorted!)

Hash Tables

O(1) Average Search Time

A hash table uses a hash function to convert a key into an array index (bucket). Average search, insert, and delete are O(1) — much faster than BST for large datasets.

HASH FUNCTION

Takes a key → returns an index (address)

Example: index = key MOD tableSize

Good hash functions spread values uniformly

Key=73, Size=10 → 73 MOD 10 = 3 → slot 3
Key=43, Size=10 → 43 MOD 10 = 3 → COLLISION!

COLLISION HANDLING

Linear probing — try next slot (index+1, +2...) until empty slot found

Chaining — each slot holds a linked list; collision = append to chain

BST vs HASH TABLE

	BST	Hash Table
Search	O(log n)	O(1) avg
Ordered?	Yes	No
Range queries	Easy	Difficult
Worst case	O(n)	O(n) collisions

Exam Practice

Cambridge-style questions

Question 1

The following values are inserted in order into an initially empty BST: 15, 8, 22, 5, 11. Draw the resulting tree and state the output of an in-order traversal. [3]

1

Root = 15. 8 < 15 → left of 15. 22 > 15 → right of 15. 5 < 15 → left, 5 < 8 → left of 8. 11 < 15 → left, 11 > 8 → right of 8.

1

Correct tree shape: 15 at root; 8 left child; 22 right child; 5 left of 8; 11 right of 8.

1

In-order traversal (L → Root → R): 5, 8, 11, 15, 22 — all values in ascending sorted order.

Common Mistakes

Don't lose easy marks

1

Confusing the three traversal orders — use the mnemonic: Pre = Root FIRST (pre-fix), In = Root IN MIDDLE (in-order = sorted), Post = Root LAST (post-fix/delete). The "Root" position gives the name.

2

Saying a hash table always has O(1) search time — it is O(1) on average, but O(n) in the worst case (all keys hash to the same bucket, long chain). This distinction is important for comparison questions with BST.

3

Building a BST by inserting in sorted order creates a degenerate tree (like a linked list — every node only has a right child). This degrades performance to O(n). Self-balancing trees (AVL, Red-Black) solve this, but CAIE typically uses standard BST insertion.

Topic Summary — 4.3.3

What You Need to Know

BINARY SEARCH TREE

Left < root < right. O(log n) avg search. In-order = sorted output. Pre: root first (copy). In: root middle (sort). Post: root last (delete).

HASH TABLES

Hash function maps key → index. O(1) avg search. Collisions: linear probing or chaining. Not ordered — can't do range queries. BST better for ordered data.

WHEN TO USE WHICH

Use hash table when: fast lookup/insert/delete, no ordering needed, e.g. symbol tables, caches. Use BST when: sorted data needed, range queries, in-order traversal required.

CSZone

Next Video

4.4.1

Sorting Algorithms

Bubble · Insertion · Merge · Quick Sort

Head to CSZone.co.uk for the complete worksheet, quiz, and interactive tools