Trees Basics
Store a tree as adjacency lists, walk it with DFS and BFS, and compute parent, depth, subtree size and diameter in one linear pass.
The problem
A tree is a set of nodes connected by edges, with no cycles and one path between any two nodes. Maps of roads between cities, folder structures and "who reports to whom" are trees.
Typical questions:
- Who is the parent of each node, and how deep is it?
- How many nodes are in the subtree below each node?
- What is the longest path in the tree (the diameter)?
1 of 11