Tree And Dynamic Connectivity Algorithms
Asked of: Software Engineer
Last updated

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 andO(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
his 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.
Featured in interview prep guides
Practice questions
- Compute Differences Between Catalog TreesDoorDash · Software Engineer · Technical Screen · Medium
- Design dynamic connectivity with alive nodesDoorDash · Software Engineer · Onsite · Medium
- Solve tree distance and design file systemDoorDash · Software Engineer · Onsite · Medium
- Count changed nodes in N-ary treesDoorDash · Software Engineer · Technical Screen · Medium
- Find max distance between alive tree nodesDoorDash · Software Engineer · Onsite · Medium
- Count clusters covered by dashersDoorDash · Software Engineer · Technical Screen · Medium
Related concepts
- Tree And Graph ConnectivityCoding & Algorithms
- Tree And Graph Modeling AlgorithmsCoding & Algorithms
- Graph Algorithms, Dependency Resolution And ConnectivityCoding & Algorithms
- Graph, Grid, And Connectivity AlgorithmsCoding & Algorithms
- DFS/BFS Tree, Graph, And Grid TraversalCoding & Algorithms
- Tree And Linked Structure AlgorithmsCoding & Algorithms