Chapter 24 Key Takeaways: Trees and Graphs
-
Trees model hierarchy; graphs model connections. Trees have one root, no cycles, and exactly one path between any two nodes. Graphs allow cycles, multiple paths, and arbitrary connectivity.
-
A binary search tree enables O(log n) search, insert, and delete — provided the tree is balanced. In-order traversal produces sorted output.
-
Unbalanced BSTs degenerate to linked lists. Inserting sorted data into a BST produces a tree of height n with O(n) operations. Always consider balanced tree variants (AVL, red-black) for real applications.
-
Three traversals, three purposes. In-order gives sorted order (BST). Pre-order captures tree structure (copying/serialization). Post-order processes children first (deletion/evaluation).
-
Adjacency matrices give O(1) edge lookup but O(V^2) space. Use for dense graphs where memory is not a concern and edge-existence queries are frequent.
-
Adjacency lists give O(V+E) space but O(degree) edge lookup. Use for sparse graphs (most real-world graphs) where memory efficiency and neighbor iteration matter.
-
DFS goes deep; BFS goes wide. DFS uses a stack (or recursion) and is good for cycle detection, topological sort, and maze generation. BFS uses a queue and finds shortest paths in unweighted graphs.
-
Dijkstra's algorithm finds shortest paths in weighted graphs with non-negative edge weights. It greedily selects the nearest unvisited vertex and updates its neighbors. O(V^2) with an array; O((V+E) log V) with a priority queue.
-
The "first child, next sibling" trick converts any N-ary tree to a binary tree, providing a memory-efficient representation for general trees with variable numbers of children.
-
Wirth's equation is vivid here. Trees and graphs are the data structures; traversal, search, and shortest path are the algorithms. Together they solve pathfinding, spell checking, category management, and dungeon exploration.