AQA 7517 4.2.5.1: Trees (including binary trees)
The free BugBot lessons that teach this point, a robot to try it on, and the past-paper questions that test it.
What it covers
A tree is a special kind of graph, and one of the most used structures in computing. File systems, web pages, compilers, game-playing programs and fast searching are all built on trees. At GCSE you met trees informally, as decision trees or folder structures; at A level you need the precise definitions and the vocabulary that goes with them.
- A tree is a graph
- Rooted trees
- Where rooted trees are used
- A rooted tree in Python
- Is it a tree?
- Binary trees
Or do it in the simulator, with tasks that mark themselves
Lessons that teach it
- A4.5 Trees Trees and graphs
Trees as connected graphs with no cycles, rooted trees and their vocabulary, binary trees and typical uses. - A4.6 Binary search trees Trees and graphs
Building, inserting and searching, O(log n) against O(n), trees stored in arrays, and deletion in outline. - A4.8 Project: plan the route Trees and graphs
Model the mat as a graph, find the shortest route with breadth-first search, and drive it.
Try it on a robot
The task from A4.5 Trees, running here. Change the program and press Run.
The specification is AQA's own document; this page says which of our lessons teach point 4.2.5.1 and is not endorsed by the board.