A tree is a connected, acyclic structure that represents a hierarchy. It has a single root node, and each child has one parent; branches may contain smaller subtrees. section 2.7
Use family relationships to read a tree:
- The root is the topmost node. section 2.7
- A parent connects directly to one or more children; children with the same parent are siblings. section 2.7
- A leaf has no children, so its degree—the number of children—is zero. section 2.7
- An edge connects two nodes, while a path is a sequence of nodes and edges. section 2.7
- Depth measures a node’s level from the root, and height measures the tree’s total height. section 2.7
A maze as a tree
Treat the maze’s starting position as the root. Each possible move becomes a child, and repeating this for every move generates branches. A path from the root to a goal leaf records the moves needed to solve the maze. section 2.7 section 2.10
Breadth-first search explores a tree depth by depth using a FIFO queue. It records each node’s parent, checks whether a neighbor is the goal, and reconstructs the path by following parents back to the root. The first path found is returned, but an uninformed search is not guaranteed to find a more optimal path. section 2.10
Inspect the labeled root, parent, child, leaf, depth, height, edge, and path relationships. section 2.7
Figure 2.19 Maze movement tree generation using BFS
Trace how BFS generates movement branches while exploring a maze. section 2.10
