Tree And Dynamic Connectivity Algorithms

What's being tested

These problems test tree traversal, hierarchical diffing, and dynamic connectivity under clear time/space bounds. You need to recognize when to use DFS/BFS, subtree aggregation, diameter reasoning, hash maps by node identity, or connected-component labeling.

Patterns & templates

• Tree diameter with filters — compute farthest alive endpoints via postorder DFS; target O(n) time and O(h) recursion space.

• Distance in trees — use LCA when parent pointers or preprocessing exist: dist(a,b)=depth[a]+depth[b]-2*depth[lca].

• N-ary tree diff — index children by stable key or ID, compare old/new recursively, and count added, deleted, changed, or moved subtrees.

• Subtree size shortcut — when a node is inserted/deleted, add its whole subtree size instead of traversing pairwise descendants.

• Connected components on grids — run DFS/BFS/Union-Find over 4-neighbor cells; count components after combining dasher coverage masks.

• Dynamic hierarchy design — maintain maps like path -> node, id -> parent, and cached metadata; state update/query complexity explicitly.

• Traversal hygiene — iterative DFS avoids stack overflow on skewed trees; recursive DFS is acceptable when height h is bounded.

Common pitfalls

Pitfall: Treating node value as identity in tree diff problems; use stable IDs/keys, because values can change independently.

Pitfall: Recomputing distances or subtree sizes from scratch per query when preprocessing or caching is expected.

Pitfall: Counting diagonal grid cells as connected when the problem expects 4-directional adjacency.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.