Depth-First Search Coding Problems: 201 Questions with Solutions
201 depth-first search coding problems — 37 easy · 127 medium · 37 hard — with solutions in 13 languages. Plus a step-by-step walkthrough and a 8-day plan.
- Problems: 201
- By difficulty: 37 easy · 127 medium · 37 hard
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
- Cost: Free on every plan; sign in to run and submit
Depth-first search follows one path as far as it goes before backing up: recursion over a tree, flood fill over a grid, connected components over a graph, and the explicit stack that replaces recursion when depth is a concern. The problems here practise the visited bookkeeping, the base cases, and the choice between returning a value up the recursion and accumulating one in place.
New to depth-first search? Read the Depth-First Search (DFS) tutorial first.
How depth-first search works, step by step
edges = A–B, A–C, B–D, B–E, C–F, D–E; start = A- Depth-first search follows one path as deep as it goes before trying another. dfs(A) is called: A is discovered 1st and pushed on the call stack.
- In dfs(A), B is unvisited, so dfs(B) is pushed on top and B is discovered 2nd. A's other neighbours wait until B's whole branch is finished.
- In dfs(B), D is unvisited, so dfs(D) is pushed on top and D is discovered 3rd. The stack always holds the path from A down to the node being explored.
- In dfs(D), E is unvisited, so dfs(E) is pushed on top and E is discovered 4th. The path is now A → B → D → E.
- E–B leads back to B, still on the stack: a back edge, which means the graph has a cycle, so it is not followed. Nothing unvisited is left around E: dfs(E) is popped and the search backtracks to D.
- Back in dfs(D), nothing unvisited is left: dfs(D) is popped and the search backtracks to B.
- Back in dfs(B), E is already finished (reached through D), so nothing unvisited is left: dfs(B) is popped and the search backtracks to A.
- Back in dfs(A), C is unvisited, so dfs(C) is pushed on top and C is discovered 5th. The search goes deep again from here.
- In dfs(C), F is unvisited, so dfs(F) is pushed on top and F is discovered 6th. That is every node found, but the open calls still have to return.
- F's only neighbour is C, its caller, so dfs(F) returns at once and the search backtracks to C.
- Back in dfs(C), nothing unvisited is left: dfs(C) is popped and the search backtracks to A.
- dfs(A) returns and the stack is empty. Discovery order: A, B, D, E, C, F; the teal edges are the calls made, the dashed one the back edge. Each node and edge is handled once: O(V + E).
Depth-First Search study plan
14 of the 201 Depth-First Search problems (4 easy, 7 medium and 3 hard) over 8 days, about 8 h 10 min in all — the pattern first, then easiest to hardest. After that, the other 187 in the full list below are practice at your own pace. Then move on to Topological Sort.
Day 1
Learn the pattern: read the essentials and step through the walkthrough above, then solve these 3.
Day 2
Medium problems: the same pattern with one twist each. Name the twist before you code.
- Binary Tree Postorder Traversal Easy
- Word Search Medium
Day 3
More mediums. Before coding each one, write down what state the pattern keeps and when it changes.
- Number of Islands Medium
- Max Area of Island Medium
Day 4
More mediums. Before coding each one, write down what state the pattern keeps and when it changes.
- Keys and Rooms Medium
- Number of Provinces Medium
Day 5
More mediums. Before coding each one, write down what state the pattern keeps and when it changes.
- Pacific Atlantic Water Flow Medium
- Surrounded Regions Medium
Day 6
Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.
- Swim in Rising Water Hard
Day 7
Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.
Day 8
Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.
Depth-First Search: the essentials
When to reach for it
Reachability, connected regions and properties of whole paths: count the islands, measure a region, decide whether a path exists, find a cycle in a directed graph. DFS does not give shortest paths in an unweighted graph, but it needs less bookkeeping than BFS, and its finishing order is what cycle detection and topological sorting rely on.
The pattern
Mark the node, then recurse into each unmarked neighbour. On a grid that may be modified, marking can mean overwriting the cell, land becoming water. Directed cycle detection needs three states, not two: unvisited, on the current path, and finished — reaching a node that is still on the current path closes a cycle.
def count_islands(grid):
rows, cols = len(grid), len(grid[0])
def sink(r, c): # 1 if (r, c) was unvisited land
if not (0 <= r < rows and 0 <= c < cols) or grid[r][c] != 1:
return 0
grid[r][c] = 0 # mark before recursing
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
sink(r + dr, c + dc)
return 1
return sum(sink(r, c) for r in range(rows) for c in range(cols))
Cost
O(V + E) time. Space is the recursion depth, up to O(V) — a million frames on a 1000 × 1000 grid of land.
Common mistakes
- Overflowing the call stack: Python stops at 1,000 frames by default, and other languages at whatever stack the process has. Use an explicit stack when depth can reach the input size.
- Marking a node after the recursive calls instead of before, so two paths enter it.
- One visited set for directed cycle detection, which mistakes a node finished on another branch for a cycle.
- Forgetting to unmark when the question is about paths rather than reachability — that is Backtracking.
Start with
- Flood Fill: one region from one cell.
- Number of Islands: one search per unvisited region.
- Number of Provinces: components from an adjacency matrix.
All depth-first search problems
Easy (37)
- Level of a Node in Binary Tree Tree, Breadth-First Search
- Count BST Nodes That Lie in a Given Range Tree, Binary Search
- Kth Largest Element in BST Tree, Stack
- Nodes at Distance K from Root Tree, Breadth-First Search
- Check if Two Trees are Isomorphic Tree, Recursion
- Check if All Leaves are at Same Level Tree, Breadth-First Search
- Children Sum in a Binary Tree Tree
- Transform to Sum Tree Tree, Recursion
- Left View of Binary Tree Tree, Breadth-First Search
- Evaluate Boolean Binary Tree Tree
- Sum of Root To Leaf Binary Numbers Tree, Bit Manipulation
- Cousins in Binary Tree Tree, Breadth-First Search
- Univalued Binary Tree Tree, Breadth-First Search
- Range Sum of BST Tree, Binary Search
- Increasing Order Search Tree Tree, Stack
- Leaf-Similar Trees Tree
- Second Minimum Node In a Binary Tree Tree
- Two Sum IV - Input is a BST Tree, Hash Table, Two Pointers
- Merge Two Binary Trees Tree, Breadth-First Search
- Subtree of Another Tree Tree, String Matching
- Binary Tree Tilt Tree
- Diameter of Binary Tree Tree
- Minimum Absolute Difference in BST Tree, Breadth-First Search
- Find Mode in Binary Search Tree Tree
- Sum of Left Leaves Tree, Breadth-First Search
- Binary Tree Paths Tree, Backtracking, String
- Invert Binary Tree Tree, Breadth-First Search
- Path Sum Tree, Breadth-First Search
- Balanced Binary Tree Tree
- Minimum Depth of Binary Tree Tree, Breadth-First Search
- Maximum Depth of Binary Tree Tree, Breadth-First Search
- Symmetric Tree Tree, Breadth-First Search
- Same Tree Tree, Breadth-First Search
- Binary Tree Postorder Traversal Tree, Stack
- Binary Tree Preorder Traversal Tree, Stack
- Binary Tree Inorder Traversal Tree, Stack
- Flood Fill Array, Matrix, Breadth-First Search
Medium (127)
- Operations on Tree Array, Hash Table, Tree
- Throne Inheritance Hash Table, Tree, Design
- Implement Magic Dictionary Hash Table, String, Trie
- Design Add and Search Words Data Structure String, Trie, Design
- Foldable Binary Tree Tree, Recursion
- K-th Largest Perfect Subtree Size in Binary Tree Tree, Sorting
- Duplicate Subtree in Binary Tree Tree, Hash Table
- Sum of Nodes on the Longest Path from Root to Leaf Tree
- Largest BST in a Binary Tree Tree, Dynamic Programming
- Median of BST Tree
- Inorder Successor in BST Tree, Binary Search
- Minimum Distance Between Two Given Nodes of a Binary Tree Tree
- Sum Tree Tree, Recursion
- Vertical Sum of Binary Tree Tree, Hash Table
- Diagonal Traversal of Binary Tree Tree, Queue
- Boundary Traversal of Binary Tree Tree
- Closest Nodes Queries in a Binary Search Tree Tree, Binary Search, Array
- Reverse Odd Levels of Binary Tree Tree, Breadth-First Search
- Amount of Time for Binary Tree to Be Infected Tree, Breadth-First Search
- Count Nodes Equal to Average of Subtree Tree
- Step-By-Step Directions From a Binary Tree Node to Another Tree, String
- Number of Good Leaf Nodes Pairs Tree
- Pseudo-Palindromic Paths in a Binary Tree Tree, Bit Manipulation
- Count Good Nodes in Binary Tree Tree, Breadth-First Search
- Longest ZigZag Path in a Binary Tree Tree, Dynamic Programming
- Linked List in Binary Tree Tree
- Maximum Product of Splitted Binary Tree Tree
- Delete Leaves With a Given Value Tree
- Sum of Nodes with Even-Valued Grandparent Tree, Breadth-First Search
- All Elements in Two Binary Search Trees Tree, Sorting
- Deepest Leaves Sum Tree, Breadth-First Search
- Binary Tree Coloring Game Tree
- Insufficient Nodes in Root to Leaf Paths Tree
- Maximum Difference Between Node and Ancestor Tree
- Smallest String Starting From Leaf String, Backtracking, Tree
- Distribute Coins in Binary Tree Tree
- Flip Equivalent Binary Trees Tree
- Smallest Subtree with all the Deepest Nodes Hash Table, Tree, Breadth-First Search
- All Nodes Distance K in Binary Tree Hash Table, Tree, Breadth-First Search
- Binary Tree Pruning Tree
- Longest Univalue Path Tree
- Trim a Binary Search Tree Tree, Recursion
- Maximum Width of Binary Tree Tree, Breadth-First Search
- Add One Row to Tree Tree, Breadth-First Search
- Convert BST to Greater Tree Tree, Binary Search
- Find Largest Value in Each Tree Row Tree, Breadth-First Search
- Find Bottom Left Tree Value Tree, Breadth-First Search
- Most Frequent Subtree Sum Hash Table, Tree
- Path Sum III Tree, Prefix Sum, Hash Table
- House Robber III Tree, Dynamic Programming
- Lowest Common Ancestor of a Binary Tree Tree
- Lowest Common Ancestor of a Binary Search Tree Tree, Binary Search
- Kth Smallest Element in a BST Tree
- Binary Tree Right Side View Tree, Breadth-First Search
- Sum Root to Leaf Numbers Tree
- Flatten Binary Tree to Linked List Tree, Stack
- Path Sum II Tree, Backtracking
- Recover Binary Search Tree Tree
- Validate Binary Search Tree Tree
- Construct String from Binary Tree Tree, String
- Remove Sub-Folders from the Filesystem Array, String, Trie
- Power Grid Maintenance Array, Hash Table, Breadth-First Search
- Count Islands With Total Value Divisible by K Array, Breadth-First Search, Union Find
- Minimum Increments to Equalize Leaf Paths Array, Dynamic Programming, Tree
- Unit Conversion I Breadth-First Search, Graph
- Maximize the Number of Target Nodes After Connecting Trees I Tree, Breadth-First Search
- Find Subtree Sizes After Changes Array, Hash Table, String
- Remove Methods From Project Breadth-First Search, Graph
- Count the Number of Good Nodes Tree
- Disconnect Path in a Binary Matrix by at Most One Flip Array, Dynamic Programming, Breadth-First Search
- Lexicographically Smallest String After Applying Operations String, Breadth-First Search, Enumeration
- Validate Binary Tree Nodes Tree, Breadth-First Search, Union Find
- Coloring A Border Array, Breadth-First Search, Matrix
- Water Connection Problem Graph
- Maximum Score After Applying Operations on a Tree Dynamic Programming, Tree
- Lexicographical Numbers Trie
- Minesweeper Array, Breadth-First Search, Matrix
- Battleships in a Board Array, Matrix
- Count Nodes With the Highest Score Array, Tree, Binary Search
- Most Profitable Path in a Tree Array, Tree, Graph
- All Ancestors of a Node in a Directed Acyclic Graph Graph, Breadth-First Search, Topological Sort
- Minimize Hamming Distance After Swap Operations Array, Union Find
- Check if There is a Valid Path in a Grid Matrix, Breadth-First Search, Union Find
- Most Stones Removed with Same Row or Column Graph, Union Find
- Water and Jug Problem Math, Breadth-First Search
- Array Nesting Array
- Course Schedule IV Graph, Topological Sort, Breadth-First Search
- Detonate the Maximum Bombs Array, Math, Graph
- Loud and Rich Array, Graph, Topological Sort
- Number of Nodes in the Sub-Tree With the Same Label Hash Table, Tree, Graph
- Minimum Fuel Cost to Report to the Capital Tree, Graph, Breadth-First Search
- Count the Number of Complete Components Graph, Union Find, Breadth-First Search
- Minimum Score of a Path Between Two Cities Graph, Union Find, Breadth-First Search
- Reachable Nodes With Restrictions Array, Tree, Graph
- Maximum Number of Fish in a Grid Array, Matrix, Breadth-First Search
- Check Knight Tour Configuration Array, Matrix, Simulation
- Find All Groups of Farmland Array, Matrix, Breadth-First Search
- Where Will the Ball Fall Array, Matrix, Simulation
- Word Search Array, String, Backtracking
- Pacific Atlantic Water Flow Array, Breadth-First Search, Matrix
- Jump Game III Array, Breadth-First Search
- Count Unreachable Pairs of Nodes in an Undirected Graph Breadth-First Search, Union Find, Graph
- Find Closest Node to Given Two Nodes Graph
- Path With Minimum Effort Array, Binary Search, Breadth-First Search
- Time Needed to Inform All Employees Tree, Breadth-First Search
- Reorder Routes to Make All Paths Lead to the City Zero Breadth-First Search, Graph
- Possible Bipartition Breadth-First Search, Union Find, Graph
- Minimum Height Trees Breadth-First Search, Graph, Topological Sort
- Detect Cycles in 2D Grid Array, Breadth-First Search, Union Find
- Number of Distinct Islands Array, Hash Table, Breadth-First Search
- Shortest Bridge Array, Breadth-First Search, Matrix
- Number of Operations to Make Network Connected Breadth-First Search, Union Find, Graph
- Count Sub Islands Array, Breadth-First Search, Union Find
- Number of Enclaves Array, Breadth-First Search, Union Find
- Find Eventual Safe States Breadth-First Search, Graph, Topological Sort
- All Paths From Source to Target Backtracking, Breadth-First Search, Graph
- Keys and Rooms Breadth-First Search, Graph
- Is Graph Bipartite? Breadth-First Search, Union Find, Graph
- Graph Valid Tree Breadth-First Search, Union Find, Graph
- Number of Connected Components in an Undirected Graph Breadth-First Search, Union Find, Graph
- Count Servers that Communicate Array, Breadth-First Search, Union Find
- Number of Closed Islands Array, Breadth-First Search, Union Find
- Surrounded Regions Array, Breadth-First Search, Union Find
- Course Schedule Graph, Topological Sort
- Number of Provinces Graph, Union Find
- Max Area of Island Array, Matrix
- Number of Islands Array, Matrix, Breadth-First Search
Hard (37)
- Maximum Path Sum Between Two Leaves Tree, Recursion
- Height of Binary Tree After Subtree Removal Queries Tree, Breadth-First Search, Array
- Maximum Sum BST in Binary Tree Tree, Dynamic Programming, Recursion
- Recover a Tree From Preorder Traversal Tree, String, Stack
- Vertical Order Traversal of a Binary Tree Tree, Breadth-First Search, Hash Table
- Binary Tree Cameras Tree, Dynamic Programming, Greedy
- Binary Tree Maximum Path Sum Tree, Dynamic Programming, Recursion
- Last Day Where You Can Still Cross Array, Binary Search, Breadth-First Search
- Maximize the Number of Target Nodes After Connecting Trees II Tree, Breadth-First Search
- Time Taken to Mark All Nodes Tree, Graph, Dynamic Programming
- Maximum Number of K-Divisible Components Tree
- Count Valid Paths in a Tree Math, Dynamic Programming, Tree
- Minimum Edge Reversals So Every Node Is Reachable Dynamic Programming, Breadth-First Search, Graph
- Minimize the Total Price of the Trips Array, Dynamic Programming, Tree
- Create Components With Same Value Array, Math, Tree
- Minimum Score After Removals on a Tree Array, Bit Manipulation, Tree
- Escape a Large Maze Array, Hash Table, Breadth-First Search
- Minimize Malware Spread II Array, Hash Table, Breadth-First Search
- Contain Virus Array, Breadth-First Search, Matrix
- Articulation Points in a Graph Graph
- Strongly Connected Components (Kosaraju's Algorithm) Graph
- Maximum Points After Collecting Coins From All Nodes Array, Dynamic Programming, Bit Manipulation
- Freedom Trail String, Dynamic Programming, Breadth-First Search
- Minimize Malware Spread Array, Hash Table, Graph
- Sum of Distances in Tree Tree, Graph, Dynamic Programming
- Longest Path With Different Adjacent Characters Array, String, Tree
- Maximum Employees to Be Invited to a Meeting Graph, Topological Sort
- Redundant Connection II Graph, Union Find
- Concatenated Words String, Dynamic Programming, Trie
- Minimum Number of Days to Disconnect Island Array, Matrix, Breadth-First Search
- Number of Increasing Paths in a Grid Array, Matrix, Dynamic Programming
- Find All People With Secret Graph, Union Find, Breadth-First Search
- Critical Connections in a Network Graph, Biconnected Component
- Making A Large Island Array, Matrix, Breadth-First Search
- Longest Increasing Path in a Matrix Array, Matrix, Dynamic Programming
- Swim in Rising Water Array, Binary Search, Breadth-First Search
- Longest Cycle in a Graph Graph, Topological Sort
Companies that ask depth-first search problems
- Amazon 186 problems on depth-first search
- Google 135 problems on depth-first search
- Microsoft 72 problems on depth-first search
- Meta 50 problems on depth-first search
- Bloomberg 13 problems on depth-first search
- Samsung 7 problems on depth-first search
- Adobe 6 problems on depth-first search
- Flipkart 6 problems on depth-first search
- LinkedIn 6 problems on depth-first search
- LiveRamp 4 problems on depth-first search
- Snapchat 4 problems on depth-first search
- Uber 4 problems on depth-first search
Next topic: Topological Sort