Trees and graphs

Graphs and how to store them, depth-first and breadth-first traversal, trees and binary search trees, the three tree traversals, and a robot that plans its shortest route across the mat.

Module A4A level8 lessons

1. A4.1 Graphs Vertices and edges; directed, undirected and weighted graphs; degree, the handshake lemma and typical uses.
2. A4.2 Adjacency matrix and adjacency list Two ways to store a graph, and choosing between them for dense and sparse graphs.
3. A4.3 Depth-first traversal Going deep and backtracking, recursively and with a stack; tracing it and what it is used for.
4. A4.4 Breadth-first traversal Level by level with a queue, shortest paths in unweighted graphs, and a breadth-first visit of the mat's zones.
5. A4.5 Trees Trees as connected graphs with no cycles, rooted trees and their vocabulary, binary trees and typical uses.
6. A4.6 Binary search trees Building, inserting and searching, O(log n) against O(n), trees stored in arrays, and deletion in outline.
7. A4.7 Tree traversals Pre-order, in-order and post-order, the outline method, expression trees and what each traversal is for.
8. A4.8 Project: plan the route Model the mat as a graph, find the shortest route with breadth-first search, and drive it.