DFS [mp]

Micro pattern¶

Description¶

Explore one branch fully before returning to another branch.

Problems¶

Graph components¶

Visit every reachable vertex before starting another component.

• DFS (DSA)
• 547. Number of Provinces (Google Prep)
• 841. Keys and Rooms (Graph Theory)
• 1466. Reorder Routes to Make All Paths Lead to the City Zero (Graph Theory)
• 797. All Paths From Source to Target (Graph Theory)
• 1192. Critical Connections in a Network (Graph Theory)
• 1306. Jump Game III (Graph Theory)
• 721. Accounts Merge (Graph Theory)
• 785. Is Graph Bipartite? (Graph Theory)

Trees¶

Process child subtrees recursively or with an explicit stack.

• 98. Validate Binary Search Tree (Top Easy)
• 104. Maximum Depth of Binary Tree (Top Easy)
• 404. Sum of Left Leaves (Google Prep)
• 297. Serialize and Deserialize Binary Tree (Top Medium)
• 236. Lowest Common Ancestor of a Binary Tree (Top Hard)
• 124. Binary Tree Maximum Path Sum (Top Hard)
• 1376. Time Needed to Inform All Employees (Graph Theory)
• 863. All Nodes Distance K in Binary Tree (Graph Theory)
• 337. House Robber III (Dynamic Programming)

Grids¶

Treat valid neighboring cells as vertices and explore connected regions.

• 79. Word Search (Top Medium)
• 200. Number of Islands (Top Medium)
• 130. Surrounded Regions (Top Hard)
• 212. Word Search II (Top Hard)
• 934. Shortest Bridge (Graph Theory)
• 1020. Number of Enclaves (Graph Theory)
• 1254. Number of Closed Islands (Graph Theory)
• 695. Max Area of Island (Graph Theory)
• 417. Pacific Atlantic Water Flow (Graph Theory)