How do trees, graphs and hash tables organise data, and what are they used for?
Trees, graphs and hash tables: binary search trees and their traversals (in-order, pre-order, post-order), graphs as adjacency matrices and adjacency lists, and hashing for direct-access tables including collision handling.
An Eduqas Component 1 answer on trees, graphs and hash tables: binary search trees and in-order, pre-order and post-order traversals, representing graphs with an adjacency matrix or adjacency list, and hashing for fast direct access with collision handling.
Reviewed by: AI editorial process; not yet individually human-reviewed
Have a quick question? Jump to the Q&A page
Jump to a section
What this dot point is asking
Eduqas wants you to describe binary search trees and their three traversals, represent a graph as an adjacency matrix or adjacency list, and explain hashing and collision handling. These structures organise data for fast search, model relationships, and give near constant-time lookup respectively.
The answer
Binary search trees and traversals
Graphs and their representations
Hash tables and collisions
Examples in context
A BST backs ordered collections where you need both fast search and easy sorted output, such as an index of words. Graphs model road networks for routing, web pages for crawling, and task dependencies for scheduling, which is why the next dot point on traversal algorithms (breadth-first and depth-first) builds directly on this one. Hash tables implement dictionaries, sets, caches and symbol tables in compilers, anywhere you need to look something up by a key almost instantly.
Try this
Q1. State the output order of an in-order traversal of a binary search tree. [1 mark]
- Cue. Ascending (sorted) order of the keys.
Q2. Give one situation where an adjacency list is preferable to an adjacency matrix. [1 mark]
- Cue. A sparse graph (few edges relative to vertices), where the list uses far less space than the matrix.
Q3. Describe what a collision is in a hash table and name one way to handle it. [2 marks]
- Cue. Two different keys hash to the same index; handle it by chaining (a linked list per slot) or by open addressing (probe for the next free slot).
Exam-style practice questions
Practice questions written in the style of WJEC Eduqas exam questions on this dot point, with worked answer explainers. The year tag is the paper they imitate, not the source.
Eduqas 20195 marksThe values are inserted, in that order, into an initially empty binary search tree. Draw the resulting tree and give the order in which the values are output by an in-order traversal.Show worked answer →
Build the tree (up to 3 marks): is the root; goes left; goes right; goes left of ; goes right of ; goes left of . So has left child (with children and ) and right child (with left child ).
In-order traversal (up to 2 marks) visits left subtree, node, right subtree, which for a binary search tree outputs the values in ascending order: .
Markers reward the correctly built tree and the sorted in-order output. The key insight is that an in-order traversal of a BST always yields a sorted sequence.
Eduqas 20214 marksExplain what a hash table is and why it gives fast lookup, and describe one way of dealing with a collision.Show worked answer →
A hash table stores key-value pairs in an array; a hash function maps each key to an index, so an item can be stored and found by computing its index directly rather than searching (up to 2 marks). This gives near constant-time access on average.
A collision occurs when two keys hash to the same index. One method is chaining: each slot holds a linked list and colliding items are appended to that list. An alternative is open addressing: probe to the next free slot (up to 2 marks).
Markers reward the index-from-key idea, why that is fast, and a correct collision-handling method (chaining or probing).
Related dot points
- Dynamic data structures: stacks (LIFO) and queues (FIFO) with their push, pop, enqueue and dequeue operations and pointer management, linear and circular queues, and singly and doubly linked lists with insertion and deletion.
An Eduqas Component 1 answer on stacks, queues and linked lists: LIFO and FIFO behaviour, push, pop, enqueue and dequeue with pointer management, the wrap-around in a circular queue, and inserting and deleting nodes in a linked list.
- Searching and traversal algorithms: linear search and binary search with their conditions and efficiency, and the breadth-first and depth-first traversals of trees and graphs.
An Eduqas Component 1 answer on searching: how linear search and binary search work, the precondition that binary search needs sorted data, their time complexities, and how breadth-first and depth-first traversals explore trees and graphs.
- Recursion and algorithmic complexity: the base case and recursive case, how recursion uses the call stack, and Big-O notation for the time and space complexity of algorithms (constant, logarithmic, linear, polynomial and exponential).
An Eduqas Component 1 answer on recursion and complexity: the base case and recursive case, how recursion uses the call stack and can cause stack overflow, and Big-O notation for measuring how an algorithm's time and space scale with input size.
- Static data structures: one- and multi-dimensional arrays, records (structs), tuples and sets, how they are stored contiguously in memory, address calculation for array elements, and choosing the appropriate structure for a task.
An Eduqas Component 1 answer on static data structures: one- and multi-dimensional arrays, records, tuples and sets, how they are stored contiguously in memory, calculating the address of an array element, and choosing the right structure for a problem.
- Organisation and structure of data: files, records and fields with key fields and file access methods, relational databases with primary and foreign keys, normalisation to third normal form, and SQL for querying and manipulating data.
An Eduqas Component 2 answer on the organisation and structure of data: files, records and fields with key fields and access methods, relational databases with primary and foreign keys, normalisation to third normal form, and writing SQL queries.