AQA 7517 4.3.4.3: Binary tree search
The free BugBot lesson that teach this point, a robot to try it on, and the past-paper questions that test it.
What it covers
At GCSE, binary search needed a sorted list. A sorted list is quick to search but slow to change: inserting an item in the middle means shifting everything after it along. A binary search tree keeps data in order and also lets new items go straight in, and it is the starting point for the search trees that databases and programming language libraries use to keep ordered collections.
- The rule
- Building a tree by inserting
- Searching
- How fast is it?
- A tree in arrays
- Deleting, in outline
Or do it in the simulator, with tasks that mark themselves
Lessons that teach it
- 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.
Try it on a robot
The task from A4.6 Binary search 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.3.4.3 and is not endorsed by the board.