Pattern 11 of 22

Depth-First Search Pattern: Template + 366 LeetCode Problems

Follow one path to its end before trying the next — the default way to explore a graph.

Easy: 41
Medium: 214
Hard: 111
Time: O(V + E)

What the depth-first search pattern is

Depth-first search commits to one branch and follows it to exhaustion before backing up, which makes it the right traversal whenever the question is about a whole component rather than about distance. Recursion is the natural expression because the call stack already is the traversal stack, but the recursion depth equals the longest path — enough to blow Python's default limit on a large grid, which is when the explicit-stack form earns its keep. The bug that costs the most time is marking nodes seen at the wrong moment: mark on discovery, when the node is first pushed or first entered, never when it is popped, or a node reachable by two edges gets queued twice and the traversal degenerates. For cycle detection in a directed graph, a two-state seen set is not enough — you need three, because a node already finished is not the same thing as a node still on the current path, and only the second means a cycle.

When to use it

You need everything reachable from a node: a connected component, an island, an enclosed region.
The problem is about paths, subtree aggregates, or values computed from children.
You are detecting a cycle in a directed graph, or classifying edges.
The graph is deep and narrow rather than wide, so a queue would hold more than the stack does.

The depth-first search template in Python

The shape, not a solution to any one problem. Adapt the condition and the summary being maintained; the skeleton stays the same across the 366 problems listed below.

PythonDepth-First Search template

def dfs(graph, start):
    seen = {start}
    stack = [start]
    order = []

    while stack:
        node = stack.pop()
        order.append(node)
        for neighbour in graph[node]:
            if neighbour not in seen:
                seen.add(neighbour)     # mark on PUSH, not on pop
                stack.append(neighbour)

    return order

Complexity characteristics

Time: O(V + E)
Auxiliary space: O(V)

Every node is marked seen once and every edge is examined once from each endpoint, so the traversal is linear in the size of the graph — on an r × c grid that is O(r·c), with four edges per cell. The space is the seen set plus the stack, and the stack holds the longest path in the graph, which is why the recursive form overflows Python's default recursion limit on a large grid while the explicit-stack form does not.

Eyes only

Meet the depth-first search problem you did not practise.

In the live round, Stealth Interview reads the problem off your screen, returns a working solution with a step-by-step explanation and its time and space complexity, and transcribes what the interviewer says. It's a desktop app for macOS and Windows, invisible to screen sharing.

Get Stealth Interview See pricing

90%Subscription

python

Please analyze this context and help me answer the question or solve the problem.

Technical interview · 45 minsolution.pyShared editor · Python 3Longest substring without repeatsMediumGiven a string s, return the length of the longest contiguous substring in which every character is unique.s = "abcabcbb"
→ 31def length_of_longest_substring(s: str) -> int:2 last_seen = {}3 left = best = 04 for right, ch in enumerate(s):5 if ch in last_seen and last_seen[ch] >= left:

python

def length_of_longest_substring(s: str) -> int:    last_seen = {}                    # char -> index    left = best = 0    for right, ch in enumerate(s):        if ch in last_seen and last_seen[ch] >= left:            left = last_seen[ch] + 1  # jump past it        last_seen[ch] = right        best = max(best, right - left + 1)    return best    last_seen = {}                    # char -> index

Approach

At each index r, the window's left edge is:

left r = max (left r -1, last[s r] + 1)

Time O(n): each character enters and leaves the window once.
Space O(min(n, k)): k is the size of the character set.

Type your message...

GPT-6.1 Terra

90%Subscription

python

Please analyze this context and help me answer the question or solve the problem.

python

def length_of_longest_substring(s: str) -> int:    last_seen = {}                    # char -> index    left = best = 0    for right, ch in enumerate(s):        if ch in last_seen and last_seen[ch] >= left:            left = last_seen[ch] + 1  # jump past it        last_seen[ch] = right        best = max(best, right - left + 1)    return best    last_seen = {}                    # char -> index

Approach

At each index r, the window's left edge is:

left r = max (left r -1, last[s r] + 1)

Time O(n): each character enters and leaves the window once.
Space O(min(n, k)): k is the size of the character set.

Type your message...

GPT-6.1 TerraClear chat

QuitEscHide+QCapture+PCrop+OSubmit+EnterPress to get answerLeft/Right+Up/Down+

90%Subscription

python

Please analyze this context and help me answer the question or solve the problem.

python

def length_of_longest_substring(s: str) -> int:    last_seen = {}                    # char -> index    left = best = 0    for right, ch in enumerate(s):        if ch in last_seen and last_seen[ch] >= left:            left = last_seen[ch] + 1  # jump past it        last_seen[ch] = right        best = max(best, right - left + 1)    return best    last_seen = {}                    # char -> index

Approach

At each index r, the window's left edge is:

left r = max (left r -1, last[s r] + 1)

Time O(n): each character enters and leaves the window once.
Space O(min(n, k)): k is the size of the character set.

Type your message...

GPT-6.1 TerraClear chat

Primary display

QuitEscHide+QCapture+PCrop+OSubmit+EnterPress to get answerLeft/Right+Up/Down+

All 366 depth-first search LeetCode problems

Every problem in the library the depth-first search pattern applies to, grouped by LeetCode's own difficulty rating. 272 of the 366 carry a complete Python solution with a worked example and complexity analysis; the rest are listed for completeness, with the LeetCode Premium ones marked.

Easy (41)

Easy problems
No.	Problem	Topics
0094	Binary Tree Inorder Traversal	Stack, Tree, Depth-First Search +1
0100	Same Tree	Tree, Depth-First Search, Breadth-First Search +1
0101	Symmetric Tree	Tree, Depth-First Search, Breadth-First Search +1
0104	Maximum Depth of Binary Tree	Tree, Depth-First Search, Breadth-First Search +1
0110	Balanced Binary Tree	Tree, Depth-First Search, Binary Tree
0111	Minimum Depth of Binary Tree	Tree, Depth-First Search, Breadth-First Search +1
0112	Path Sum	Tree, Depth-First Search, Breadth-First Search +1
0144	Binary Tree Preorder Traversal	Stack, Tree, Depth-First Search +1
0145	Binary Tree Postorder Traversal	Stack, Tree, Depth-First Search +1
0226	Invert Binary Tree	Tree, Depth-First Search, Breadth-First Search +1
0257	Binary Tree Paths	Tree, Depth-First Search, String +2
0404	Sum of Left Leaves	Tree, Depth-First Search, Breadth-First Search +1
0463	Island Perimeter	Depth-First Search, Breadth-First Search, Array +1
0501	Find Mode in Binary Search Tree	Tree, Depth-First Search, Binary Search Tree +1
0530	Minimum Absolute Difference in BST	Tree, Depth-First Search, Breadth-First Search +2
0543	Diameter of Binary Tree	Tree, Depth-First Search, Binary Tree
0559	Maximum Depth of N-ary Tree	Tree, Depth-First Search, Breadth-First Search
0563	Binary Tree Tilt	Tree, Depth-First Search, Binary Tree
0572	Subtree of Another Tree	Tree, Depth-First Search, Binary Tree +2
0589	N-ary Tree Preorder Traversal	Stack, Tree, Depth-First Search
0590	N-ary Tree Postorder Traversal	Stack, Tree, Depth-First Search
0617	Merge Two Binary Trees	Tree, Depth-First Search, Breadth-First Search +1
0637	Average of Levels in Binary Tree	Tree, Depth-First Search, Breadth-First Search +1
0653	Two Sum IV - Input is a BST	Tree, Depth-First Search, Breadth-First Search +4
0671	Second Minimum Node In a Binary Tree	Tree, Depth-First Search, Binary Tree
0733	Flood Fill	Depth-First Search, Breadth-First Search, Array +1
0872	Leaf-Similar Trees	Tree, Depth-First Search, Binary Tree
0270	Closest Binary Search Tree ValuePremium	Tree, Depth-First Search, Binary Search Tree +2
0783	Minimum Distance Between BST Nodes	Tree, Depth-First Search, Breadth-First Search +2
0897	Increasing Order Search Tree	Stack, Tree, Depth-First Search +2
0938	Range Sum of BST	Tree, Depth-First Search, Binary Search Tree +1
0965	Univalued Binary Tree	Tree, Depth-First Search, Breadth-First Search +1
0993	Cousins in Binary Tree	Tree, Depth-First Search, Breadth-First Search +1
0997	Find the Town Judge	Graph, Array, Hash Table
1022	Sum of Root To Leaf Binary Numbers	Tree, Depth-First Search, Binary Tree
1379	Find a Corresponding Node of a Binary Tree in a Clone of That Tree	Tree, Depth-First Search, Breadth-First Search +1
1469	Find All The Lonely NodesPremium	Tree, Depth-First Search, Breadth-First Search +1
1791	Find Center of Star Graph	Graph
1971	Find if Path Exists in Graph	Depth-First Search, Breadth-First Search, Union Find +1
2331	Evaluate Boolean Binary Tree	Tree, Depth-First Search, Binary Tree
2689	Extract Kth Character From The Rope TreePremium	Tree, Depth-First Search, Binary Tree

Medium (214)

Medium problems
No.	Problem	Topics
0079	Word Search	Depth-First Search, Array, String +2
0098	Validate Binary Search Tree	Tree, Depth-First Search, Binary Search Tree +1
0099	Recover Binary Search Tree	Tree, Depth-First Search, Binary Search Tree +1
0113	Path Sum II	Tree, Depth-First Search, Backtracking +1
0114	Flatten Binary Tree to Linked List	Stack, Tree, Depth-First Search +2
0116	Populating Next Right Pointers in Each Node	Tree, Depth-First Search, Breadth-First Search +2
0117	Populating Next Right Pointers in Each Node II	Tree, Depth-First Search, Breadth-First Search +2
0129	Sum Root to Leaf Numbers	Tree, Depth-First Search, Binary Tree
0130	Surrounded Regions	Depth-First Search, Breadth-First Search, Union Find +2
0133	Clone Graph	Depth-First Search, Breadth-First Search, Graph +1
0199	Binary Tree Right Side View	Tree, Depth-First Search, Breadth-First Search +1
0200	Number of Islands	Depth-First Search, Breadth-First Search, Union Find +2
0207	Course Schedule	Depth-First Search, Breadth-First Search, Graph +1
0210	Course Schedule II	Depth-First Search, Breadth-First Search, Graph +1
0211	Design Add and Search Words Data Structure	Depth-First Search, Design, Trie +1
0230	Kth Smallest Element in a BST	Tree, Depth-First Search, Binary Search Tree +1
0235	Lowest Common Ancestor of a Binary Search Tree	Tree, Depth-First Search, Binary Search Tree +1
0236	Lowest Common Ancestor of a Binary Tree	Tree, Depth-First Search, Binary Tree
0310	Minimum Height Trees	Depth-First Search, Breadth-First Search, Graph +1
0337	House Robber III	Tree, Depth-First Search, Dynamic Programming +1
0341	Flatten Nested List Iterator	Stack, Tree, Depth-First Search +3
0365	Water and Jug Problem	Depth-First Search, Breadth-First Search, Math
0385	Mini Parser	Stack, Depth-First Search, String
0386	Lexicographical Numbers	Depth-First Search, Trie
0388	Longest Absolute File Path	Stack, Depth-First Search, String
0399	Evaluate Division	Depth-First Search, Breadth-First Search, Union Find +4
0417	Pacific Atlantic Water Flow	Depth-First Search, Breadth-First Search, Array +1
0419	Battleships in a Board	Depth-First Search, Array, Matrix
0430	Flatten a Multilevel Doubly Linked List	Depth-First Search, Linked List, Doubly-Linked List
0437	Path Sum III	Tree, Depth-First Search, Binary Tree
0449	Serialize and Deserialize BST	Tree, Depth-First Search, Breadth-First Search +4
0508	Most Frequent Subtree Sum	Tree, Depth-First Search, Hash Table +1
0513	Find Bottom Left Tree Value	Tree, Depth-First Search, Breadth-First Search +1
0515	Find Largest Value in Each Tree Row	Tree, Depth-First Search, Breadth-First Search +1
0529	Minesweeper	Depth-First Search, Breadth-First Search, Array +1
0538	Convert BST to Greater Tree	Tree, Depth-First Search, Binary Search Tree +1
0547	Number of Provinces	Depth-First Search, Breadth-First Search, Union Find +1
0565	Array Nesting	Depth-First Search, Array
0606	Construct String from Binary Tree	Tree, Depth-First Search, String +1
0623	Add One Row to Tree	Tree, Depth-First Search, Breadth-First Search +1
0652	Find Duplicate Subtrees	Tree, Depth-First Search, Hash Table +1
0655	Print Binary Tree	Tree, Depth-First Search, Breadth-First Search +1
0662	Maximum Width of Binary Tree	Tree, Depth-First Search, Breadth-First Search +1
0669	Trim a Binary Search Tree	Tree, Depth-First Search, Binary Search Tree +1
0672	Bulb Switcher II	Bit Manipulation, Depth-First Search, Breadth-First Search +1
0676	Implement Magic Dictionary	Depth-First Search, Design, Trie +2
0684	Redundant Connection	Depth-First Search, Breadth-First Search, Union Find +1
0687	Longest Univalue Path	Tree, Depth-First Search, Binary Tree
0690	Employee Importance	Tree, Depth-First Search, Breadth-First Search +2
0695	Max Area of Island	Depth-First Search, Breadth-First Search, Union Find +2
0721	Accounts Merge	Depth-First Search, Breadth-First Search, Union Find +4
0743	Network Delay Time	Depth-First Search, Breadth-First Search, Graph +2
0787	Cheapest Flights Within K Stops	Depth-First Search, Breadth-First Search, Graph +3
0841	Keys and Rooms	Depth-First Search, Breadth-First Search, Graph
1161	Maximum Level Sum of a Binary Tree	Tree, Depth-First Search, Breadth-First Search +1
1372	Longest ZigZag Path in a Binary Tree	Tree, Depth-First Search, Dynamic Programming +1
1448	Count Good Nodes in Binary Tree	Tree, Depth-First Search, Breadth-First Search +1
1466	Reorder Routes to Make All Paths Lead to the City Zero	Depth-First Search, Breadth-First Search, Graph
1584	Min Cost to Connect All Points	Union Find, Graph, Array +1
0156	Binary Tree Upside DownPremium	Tree, Depth-First Search, Binary Tree
0250	Count Univalue SubtreesPremium	Tree, Depth-First Search, Binary Tree
0261	Graph Valid TreePremium	Depth-First Search, Breadth-First Search, Union Find +1
0277	Find the CelebrityPremium	Graph, Two Pointers, Interactive
0285	Inorder Successor in BSTPremium	Tree, Depth-First Search, Binary Search Tree +1
0298	Binary Tree Longest Consecutive SequencePremium	Tree, Depth-First Search, Binary Tree
0314	Binary Tree Vertical Order TraversalPremium	Tree, Depth-First Search, Breadth-First Search +3
0323	Number of Connected Components in an Undirected GraphPremium	Depth-First Search, Breadth-First Search, Union Find +1
0333	Largest BST SubtreePremium	Tree, Depth-First Search, Binary Search Tree +2
0339	Nested List Weight SumPremium	Depth-First Search, Breadth-First Search
0364	Nested List Weight Sum IIPremium	Stack, Depth-First Search, Breadth-First Search
0366	Find Leaves of Binary TreePremium	Tree, Depth-First Search, Binary Tree
0426	Convert Binary Search Tree to Sorted Doubly Linked ListPremium	Stack, Tree, Depth-First Search +4
0444	Sequence ReconstructionPremium	Graph, Topological Sort, Array
0490	The MazePremium	Depth-First Search, Breadth-First Search, Array +1
0505	The Maze IIPremium	Depth-First Search, Breadth-First Search, Graph +4
0536	Construct Binary Tree from StringPremium	Stack, Tree, Depth-First Search +2
0545	Boundary of Binary TreePremium	Tree, Depth-First Search, Binary Tree
0549	Binary Tree Longest Consecutive Sequence IIPremium	Tree, Depth-First Search, Binary Tree
0582	Kill ProcessPremium	Tree, Depth-First Search, Breadth-First Search +2
0663	Equal Tree PartitionPremium	Tree, Depth-First Search, Binary Tree
0666	Path Sum IVPremium	Tree, Depth-First Search, Array +2
0694	Number of Distinct IslandsPremium	Depth-First Search, Breadth-First Search, Union Find +2
0737	Sentence Similarity IIPremium	Depth-First Search, Breadth-First Search, Union Find +3
0742	Closest Leaf in a Binary TreePremium	Tree, Depth-First Search, Breadth-First Search +1
0785	Is Graph Bipartite?	Depth-First Search, Breadth-First Search, Union Find +1
0797	All Paths From Source to Target	Depth-First Search, Breadth-First Search, Graph +1
0802	Find Eventual Safe States	Depth-First Search, Breadth-First Search, Graph +1
0814	Binary Tree Pruning	Tree, Depth-First Search, Binary Tree
0851	Loud and Rich	Depth-First Search, Graph, Topological Sort +1
0863	All Nodes Distance K in Binary Tree	Tree, Depth-First Search, Breadth-First Search +2
0865	Smallest Subtree with all the Deepest Nodes	Tree, Depth-First Search, Breadth-First Search +2
0886	Possible Bipartition	Depth-First Search, Breadth-First Search, Union Find +1
0934	Shortest Bridge	Depth-First Search, Breadth-First Search, Array +1
0947	Most Stones Removed with Same Row or Column	Depth-First Search, Union Find, Graph +1
0951	Flip Equivalent Binary Trees	Tree, Depth-First Search, Binary Tree
0959	Regions Cut By Slashes	Depth-First Search, Breadth-First Search, Union Find +3
0971	Flip Binary Tree To Match Preorder Traversal	Tree, Depth-First Search, Binary Tree
0979	Distribute Coins in Binary Tree	Tree, Depth-First Search, Binary Tree
0988	Smallest String Starting From Leaf	Tree, Depth-First Search, String +2
0990	Satisfiability of Equality Equations	Union Find, Graph, Array +1
1020	Number of Enclaves	Depth-First Search, Breadth-First Search, Union Find +2
1026	Maximum Difference Between Node and Ancestor	Tree, Depth-First Search, Binary Tree
1034	Coloring A Border	Depth-First Search, Breadth-First Search, Array +1
1038	Binary Search Tree to Greater Sum Tree	Tree, Depth-First Search, Binary Search Tree +1
1042	Flower Planting With No Adjacent	Depth-First Search, Breadth-First Search, Graph
1059	All Paths from Source Lead to DestinationPremium	Graph, Topological Sort
1080	Insufficient Nodes in Root to Leaf Paths	Tree, Depth-First Search, Binary Tree
1102	Path With Maximum Minimum ValuePremium	Depth-First Search, Breadth-First Search, Union Find +4
1110	Delete Nodes And Return Forest	Tree, Depth-First Search, Array +2
1120	Maximum Average SubtreePremium	Tree, Depth-First Search, Binary Tree
1123	Lowest Common Ancestor of Deepest Leaves	Tree, Depth-First Search, Breadth-First Search +2
1129	Shortest Path with Alternating Colors	Breadth-First Search, Graph
1135	Connecting Cities With Minimum CostPremium	Union Find, Graph, Minimum Spanning Tree +1
1136	Parallel CoursesPremium	Graph, Topological Sort
1145	Binary Tree Coloring Game	Tree, Depth-First Search, Binary Tree
1202	Smallest String With Swaps	Depth-First Search, Breadth-First Search, Union Find +4
1214	Two Sum BSTsPremium	Stack, Tree, Depth-First Search +4
1233	Remove Sub-Folders from the Filesystem	Depth-First Search, Trie, Array +1
1236	Web CrawlerPremium	Depth-First Search, Breadth-First Search, String +1
1242	Web Crawler MultithreadedPremium	Depth-First Search, Breadth-First Search, Concurrency
1245	Tree DiameterPremium	Tree, Depth-First Search, Breadth-First Search +2
1254	Number of Closed Islands	Depth-First Search, Breadth-First Search, Union Find +2
1257	Smallest Common RegionPremium	Tree, Depth-First Search, Breadth-First Search +3
1261	Find Elements in a Contaminated Binary Tree	Tree, Depth-First Search, Breadth-First Search +3
1267	Count Servers that Communicate	Depth-First Search, Breadth-First Search, Union Find +3
1273	Delete Tree NodesPremium	Tree, Depth-First Search, Breadth-First Search +1
1302	Deepest Leaves Sum	Tree, Depth-First Search, Breadth-First Search +1
1305	All Elements in Two Binary Search Trees	Tree, Depth-First Search, Binary Search Tree +2
1306	Jump Game III	Depth-First Search, Breadth-First Search, Array
1311	Get Watched Videos by Your Friends	Breadth-First Search, Graph, Array +2
1315	Sum of Nodes with Even-Valued Grandparent	Tree, Depth-First Search, Breadth-First Search +1
1319	Number of Operations to Make Network Connected	Depth-First Search, Breadth-First Search, Union Find +1
1325	Delete Leaves With a Given Value	Tree, Depth-First Search, Binary Tree
1334	Find the City With the Smallest Number of Neighbors at a Threshold Distance	Graph, Dynamic Programming, Shortest Path
1339	Maximum Product of Splitted Binary Tree	Tree, Depth-First Search, Binary Tree
1361	Validate Binary Tree Nodes	Tree, Depth-First Search, Breadth-First Search +3
1367	Linked List in Binary Tree	Tree, Depth-First Search, Linked List +1
1376	Time Needed to Inform All Employees	Tree, Depth-First Search, Breadth-First Search
1382	Balance a Binary Search Tree	Greedy, Tree, Depth-First Search +3
1391	Check if There is a Valid Path in a Grid	Depth-First Search, Breadth-First Search, Union Find +2
1430	Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary TreePremium	Tree, Depth-First Search, Breadth-First Search +1
1443	Minimum Time to Collect All Apples in a Tree	Tree, Depth-First Search, Breadth-First Search +1
1457	Pseudo-Palindromic Paths in a Binary Tree	Bit Manipulation, Tree, Depth-First Search +2
1462	Course Schedule IV	Depth-First Search, Breadth-First Search, Graph +1
1485	Clone Binary Tree With Random PointerPremium	Tree, Depth-First Search, Breadth-First Search +2
1490	Clone N-ary TreePremium	Tree, Depth-First Search, Breadth-First Search +1
1506	Find Root of N-Ary TreePremium	Bit Manipulation, Tree, Depth-First Search +1
1514	Path with Maximum Probability	Graph, Array, Shortest Path +1
1519	Number of Nodes in the Sub-Tree With the Same Label	Tree, Depth-First Search, Breadth-First Search +2
1522	Diameter of N-Ary TreePremium	Tree, Depth-First Search
1530	Number of Good Leaf Nodes Pairs	Tree, Depth-First Search, Binary Tree
1557	Minimum Number of Vertices to Reach All Nodes	Graph
1559	Detect Cycles in 2D Grid	Depth-First Search, Breadth-First Search, Union Find +2
1600	Throne Inheritance	Tree, Depth-First Search, Design +1
1612	Check If Two Expression Trees are EquivalentPremium	Tree, Depth-First Search, Hash Table +2
1615	Maximal Network Rank	Graph
1625	Lexicographically Smallest String After Applying Operations	Depth-First Search, Breadth-First Search, String +1
1631	Path With Minimum Effort	Depth-First Search, Breadth-First Search, Union Find +4
1644	Lowest Common Ancestor of a Binary Tree IIPremium	Tree, Depth-First Search, Binary Tree
1660	Correct a Binary TreePremium	Tree, Depth-First Search, Breadth-First Search +2
1666	Change the Root of a Binary TreePremium	Tree, Depth-First Search, Binary Tree
1676	Lowest Common Ancestor of a Binary Tree IVPremium	Tree, Depth-First Search, Hash Table +1
1722	Minimize Hamming Distance After Swap Operations	Depth-First Search, Union Find, Array
1740	Find Distance in a Binary TreePremium	Tree, Depth-First Search, Breadth-First Search +2
1743	Restore the Array From Adjacent Pairs	Depth-First Search, Array, Hash Table
1778	Shortest Path in a Hidden GridPremium	Depth-First Search, Breadth-First Search, Array +2
1786	Number of Restricted Paths From First to Last Node	Graph, Topological Sort, Dynamic Programming +2
1810	Minimum Path Cost in a Hidden GridPremium	Depth-First Search, Breadth-First Search, Graph +5
1820	Maximum Number of Accepted InvitationsPremium	Depth-First Search, Graph, Array +1
1858	Longest Word With All PrefixesPremium	Depth-First Search, Trie, Array +1
1905	Count Sub Islands	Depth-First Search, Breadth-First Search, Union Find +2
1973	Count Nodes Equal to Sum of DescendantsPremium	Tree, Depth-First Search, Binary Tree
1976	Number of Ways to Arrive at Destination	Graph, Topological Sort, Dynamic Programming +1
1992	Find All Groups of Farmland	Depth-First Search, Breadth-First Search, Array +1
1993	Operations on Tree	Tree, Depth-First Search, Breadth-First Search +3
2039	The Time When the Network Becomes Idle	Breadth-First Search, Graph, Array
2049	Count Nodes With the Highest Score	Tree, Depth-First Search, Array +1
2077	Paths in Maze That Lead to Same RoomPremium	Graph
2093	Minimum Cost to Reach City With DiscountsPremium	Graph, Shortest Path, Heap (Priority Queue)
2096	Step-By-Step Directions From a Binary Tree Node to Another	Tree, Depth-First Search, String +1
2101	Detonate the Maximum Bombs	Depth-First Search, Breadth-First Search, Graph +3
2115	Find All Possible Recipes from Given Supplies	Graph, Topological Sort, Array +2
2192	All Ancestors of a Node in a Directed Acyclic Graph	Depth-First Search, Breadth-First Search, Graph +1
2265	Count Nodes Equal to Average of Subtree	Tree, Depth-First Search, Binary Tree
2285	Maximum Total Importance of Roads	Greedy, Graph, Sorting +1
2297	Jump Game VIIIPremium	Stack, Graph, Array +3
2316	Count Unreachable Pairs of Nodes in an Undirected Graph	Depth-First Search, Breadth-First Search, Union Find +1
2359	Find Closest Node to Given Two Nodes	Depth-First Search, Graph
2368	Reachable Nodes With Restrictions	Tree, Depth-First Search, Breadth-First Search +4
2374	Node With Highest Edge Score	Graph, Hash Table
2378	Choose Edges to Maximize Score in a TreePremium	Tree, Depth-First Search, Dynamic Programming
2385	Amount of Time for Binary Tree to Be Infected	Tree, Depth-First Search, Breadth-First Search +2
2415	Reverse Odd Levels of Binary Tree	Tree, Depth-First Search, Breadth-First Search +1
2445	Number of Nodes With Value OnePremium	Tree, Depth-First Search, Breadth-First Search +2
2467	Most Profitable Path in a Tree	Tree, Depth-First Search, Breadth-First Search +2
2473	Minimum Cost to Buy ApplesPremium	Graph, Array, Shortest Path +1
2476	Closest Nodes Queries in a Binary Search Tree	Tree, Depth-First Search, Binary Search Tree +3
2477	Minimum Fuel Cost to Report to the Capital	Tree, Depth-First Search, Breadth-First Search +1
2492	Minimum Score of a Path Between Two Cities	Depth-First Search, Breadth-First Search, Union Find +1
2497	Maximum Star Sum of a Graph	Greedy, Graph, Array +2
2556	Disconnect Path in a Binary Matrix by at Most One Flip	Depth-First Search, Breadth-First Search, Array +2
2596	Check Knight Tour Configuration	Depth-First Search, Breadth-First Search, Array +2
2641	Cousins in Binary Tree II	Tree, Depth-First Search, Breadth-First Search +2
2658	Maximum Number of Fish in a Grid	Depth-First Search, Breadth-First Search, Union Find +2
2662	Minimum Cost of a Path With Special Roads	Graph, Array, Shortest Path +1
2685	Count the Number of Complete Components	Depth-First Search, Breadth-First Search, Union Find +1
2737	Find the Closest Marked NodePremium	Graph, Array, Shortest Path +1
2764	Is Array a Preorder of Some ‌Binary TreePremium	Stack, Tree, Depth-First Search +1
2773	Height of Special Binary TreePremium	Tree, Depth-First Search, Breadth-First Search +1
2775	Undefined to NullPremium	JavaScript
2852	Sum of Remoteness of All CellsPremium	Depth-First Search, Breadth-First Search, Union Find +3
2924	Find Champion II	Graph
2925	Maximum Score After Applying Operations on a Tree	Tree, Depth-First Search, Dynamic Programming
2976	Minimum Cost to Convert String I	Graph, Array, String +1

Hard (111)

Hard problems
No.	Problem	Topics
0124	Binary Tree Maximum Path Sum	Tree, Depth-First Search, Dynamic Programming +1
0297	Serialize and Deserialize Binary Tree	Tree, Depth-First Search, Breadth-First Search +3
0329	Longest Increasing Path in a Matrix	Depth-First Search, Breadth-First Search, Graph +5
0332	Reconstruct Itinerary	Depth-First Search, Graph, Eulerian Circuit
0472	Concatenated Words	Depth-First Search, Trie, Array +3
0514	Freedom Trail	Depth-First Search, Breadth-First Search, String +1
0685	Redundant Connection II	Depth-First Search, Breadth-First Search, Union Find +1
0749	Contain Virus	Depth-First Search, Breadth-First Search, Array +2
0778	Swim in Rising Water	Depth-First Search, Breadth-First Search, Union Find +4
0269	Alien DictionaryPremium	Depth-First Search, Breadth-First Search, Graph +3
0272	Closest Binary Search Tree Value IIPremium	Stack, Tree, Depth-First Search +4
0302	Smallest Rectangle Enclosing Black PixelsPremium	Depth-First Search, Breadth-First Search, Array +2
0428	Serialize and Deserialize N-ary TreePremium	Tree, Depth-First Search, Breadth-First Search +1
0431	Encode N-ary Tree to Binary TreePremium	Tree, Depth-First Search, Breadth-First Search +2
0499	The Maze IIIPremium	Depth-First Search, Breadth-First Search, Graph +5
0631	Design Excel Sum FormulaPremium	Graph, Design, Topological Sort +4
0642	Design Search Autocomplete SystemPremium	Depth-First Search, Design, Trie +4
0711	Number of Distinct Islands IIPremium	Depth-First Search, Breadth-First Search, Union Find +2
0753	Cracking the Safe	Depth-First Search, Graph, Eulerian Circuit
0765	Couples Holding Hands	Greedy, Depth-First Search, Breadth-First Search +2
0827	Making A Large Island	Depth-First Search, Breadth-First Search, Union Find +2
0834	Sum of Distances in Tree	Tree, Depth-First Search, Graph +1
0839	Similar String Groups	Depth-First Search, Breadth-First Search, Union Find +3
0847	Shortest Path Visiting All Nodes	Bit Manipulation, Breadth-First Search, Graph +2
0882	Reachable Nodes In Subdivided Graph	Graph, Shortest Path, Heap (Priority Queue)
0913	Cat and Mouse	Graph, Topological Sort, Memoization +3
0924	Minimize Malware Spread	Depth-First Search, Breadth-First Search, Union Find +3
0928	Minimize Malware Spread II	Depth-First Search, Breadth-First Search, Union Find +3
0968	Binary Tree Cameras	Tree, Depth-First Search, Dynamic Programming +1
0987	Vertical Order Traversal of a Binary Tree	Tree, Depth-First Search, Breadth-First Search +3
1028	Recover a Tree From Preorder Traversal	Tree, Depth-First Search, String +1
1036	Escape a Large Maze	Depth-First Search, Breadth-First Search, Array +1
1153	String Transforms Into Another StringPremium	Graph, Hash Table, String
1168	Optimize Water Distribution in a VillagePremium	Union Find, Graph, Minimum Spanning Tree +1
1192	Critical Connections in a Network	Depth-First Search, Graph, Biconnected Component
1203	Sort Items by Groups Respecting Dependencies	Depth-First Search, Breadth-First Search, Graph +1
1298	Maximum Candies You Can Get from Boxes	Breadth-First Search, Graph, Array
1368	Minimum Cost to Make at Least One Valid Path in a Grid	Breadth-First Search, Graph, Array +3
1373	Maximum Sum BST in Binary Tree	Tree, Depth-First Search, Binary Search Tree +2
1377	Frog Position After T Seconds	Tree, Depth-First Search, Breadth-First Search +1
1483	Kth Ancestor of a Tree Node	Bit Manipulation, Tree, Depth-First Search +4
1489	Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree	Union Find, Graph, Minimum Spanning Tree +2
1494	Parallel Courses II	Bit Manipulation, Graph, Dynamic Programming +1
1516	Move Sub-Tree of N-Ary TreePremium	Tree, Depth-First Search
1548	The Most Similar Path in a GraphPremium	Graph, Dynamic Programming
1568	Minimum Number of Days to Disconnect Island	Depth-First Search, Breadth-First Search, Array +2
1579	Remove Max Number of Edges to Keep Graph Fully Traversable	Union Find, Graph
1591	Strange Printer II	Graph, Topological Sort, Array +1
1632	Rank Transform of a Matrix	Union Find, Graph, Topological Sort +3
1697	Checking Existence of Edge Length Limited Paths	Union Find, Graph, Array +2
1719	Number Of Ways To Reconstruct A Tree	Tree, Graph
1724	Checking Existence of Edge Length Limited Paths IIPremium	Union Find, Graph, Minimum Spanning Tree
1728	Cat and Mouse II	Graph, Topological Sort, Memoization +5
1761	Minimum Degree of a Connected Trio in a Graph	Graph, Enumeration
1766	Tree of Coprimes	Tree, Depth-First Search, Array +2
1782	Count Pairs Of Nodes	Graph, Array, Hash Table +4
1857	Largest Color Value in a Directed Graph	Graph, Topological Sort, Memoization +3
1916	Count Ways to Build Rooms in an Ant Colony	Tree, Graph, Topological Sort +3
1928	Minimum Cost to Reach Destination in Time	Graph, Array, Dynamic Programming
1932	Merge BSTs to Create Single BST	Tree, Depth-First Search, Hash Table +2
1938	Maximum Genetic Difference Query	Bit Manipulation, Depth-First Search, Trie +2
1970	Last Day Where You Can Still Cross	Depth-First Search, Breadth-First Search, Union Find +3
2003	Smallest Missing Genetic Value in Each Subtree	Tree, Depth-First Search, Union Find +1
2045	Second Minimum Time to Reach Destination	Breadth-First Search, Graph, Shortest Path
2050	Parallel Courses III	Graph, Topological Sort, Array +1
2065	Maximum Path Quality of a Graph	Graph, Array, Backtracking
2076	Process Restricted Friend Requests	Union Find, Graph
2092	Find All People With Secret	Depth-First Search, Breadth-First Search, Union Find +2
2097	Valid Arrangement of Pairs	Depth-First Search, Graph, Eulerian Circuit
2123	Minimum Operations to Remove Adjacent Ones in MatrixPremium	Graph, Array, Matrix
2127	Maximum Employees to Be Invited to a Meeting	Depth-First Search, Graph, Topological Sort
2203	Minimum Weighted Subgraph With the Required Paths	Graph, Shortest Path
2204	Distance to a Cycle in Undirected GraphPremium	Depth-First Search, Breadth-First Search, Union Find +1
2242	Maximum Score of a Node Sequence	Graph, Array, Enumeration +1
2246	Longest Path With Different Adjacent Characters	Tree, Depth-First Search, Graph +3
2247	Maximum Cost of Trip With K HighwaysPremium	Bit Manipulation, Graph, Dynamic Programming +1
2277	Closest Node to Path in TreePremium	Tree, Depth-First Search, Breadth-First Search +1
2290	Minimum Obstacle Removal to Reach Corner	Breadth-First Search, Graph, Array +3
2307	Check for Contradictions in EquationsPremium	Depth-First Search, Union Find, Graph +1
2313	Minimum Flips in Binary Tree to Get ResultPremium	Tree, Depth-First Search, Dynamic Programming +1
2322	Minimum Score After Removals on a Tree	Bit Manipulation, Tree, Depth-First Search +1
2328	Number of Increasing Paths in a Grid	Depth-First Search, Breadth-First Search, Graph +5
2360	Longest Cycle in a Graph	Depth-First Search, Breadth-First Search, Graph +1
2371	Minimize Maximum Value in a GridPremium	Union Find, Graph, Topological Sort +3
2392	Build a Matrix With Conditions	Graph, Topological Sort, Array +1
2421	Number of Good Paths	Tree, Union Find, Graph +3
2440	Create Components With Same Value	Tree, Depth-First Search, Array +2
2458	Height of Binary Tree After Subtree Removal Queries	Tree, Depth-First Search, Breadth-First Search +2
2479	Maximum XOR of Two Non-Overlapping SubtreesPremium	Tree, Depth-First Search, Graph +1
2493	Divide Nodes Into the Maximum Number of Groups	Depth-First Search, Breadth-First Search, Union Find +1
2508	Add Edges to Make Degrees of All Nodes Even	Graph, Hash Table
2538	Difference Between Maximum and Minimum Price Sum	Tree, Depth-First Search, Array +1
2577	Minimum Time to Visit a Cell In a Grid	Breadth-First Search, Graph, Array +3
2581	Count Number of Possible Root Nodes	Tree, Depth-First Search, Array +2
2603	Collect Coins in a Tree	Tree, Graph, Topological Sort +1
2608	Shortest Cycle in a Graph	Breadth-First Search, Graph
2642	Design Graph With Shortest Path Calculator	Graph, Design, Shortest Path +1
2646	Minimize the Total Price of the Trips	Tree, Depth-First Search, Graph +2
2699	Modify Graph Edge Weights	Graph, Shortest Path, Heap (Priority Queue)
2714	Find Shortest Path with K HopsPremium	Graph, Shortest Path, Heap (Priority Queue)
2791	Count Paths That Can Form a Palindrome in a Tree	Bit Manipulation, Tree, Depth-First Search +2
2792	Count Nodes That Are Great EnoughPremium	Tree, Depth-First Search, Divide and Conquer +1
2846	Minimum Edge Weight Equilibrium Queries in a Tree	Tree, Graph, Array +1
2858	Minimum Edge Reversals So Every Node Is Reachable	Depth-First Search, Breadth-First Search, Graph +1
2867	Count Valid Paths in a Tree	Tree, Depth-First Search, Math +2
2872	Maximum Number of K-Divisible Components	Tree, Depth-First Search
2876	Count Visited Nodes in a Directed Graph	Graph, Memoization, Dynamic Programming
2920	Maximum Points After Collecting Coins From All Nodes	Bit Manipulation, Tree, Depth-First Search +3
2959	Number of Possible Sets of Closing Branches	Bit Manipulation, Graph, Enumeration +2
2973	Find Number of Coins to Place in Tree Nodes	Tree, Depth-First Search, Dynamic Programming +2
2977	Minimum Cost to Convert String II	Graph, Trie, Array +3

Depth-First Search pattern FAQ

What is the depth-first search pattern?

How many LeetCode problems use the depth-first search pattern?

This page lists 366 LeetCode problems that the depth-first search pattern applies to: 41 Easy, 214 Medium and 111 Hard. 272 of them carry a complete Python solution with complexity analysis.

What is the time complexity of the depth-first search pattern?

O(V + E) time and O(V) space. Every node is marked seen once and every edge is examined once from each endpoint, so the traversal is linear in the size of the graph — on an r × c grid that is O(r·c), with four edges per cell. The space is the seen set plus the stack, and the stack holds the longest path in the graph, which is why the recursive form overflows Python's default recursion limit on a large grid while the explicit-stack form does not.

When should I use the depth-first search pattern in an interview?

You need everything reachable from a node: a connected component, an island, an enclosed region. The problem is about paths, subtree aggregates, or values computed from children.

Which depth-first search problem should I start with?

LeetCode 94. Binary Tree Inorder Traversal is the lowest-numbered Easy problem on this page, which makes it the usual starting point: the technique is visible without the problem's own complications getting in the way.

What patterns are related to depth-first search?

Breadth-First Search, Backtracking, Tree Traversal, Matrix and Grid. Problems frequently sit in more than one of these, and the overlap is where the interesting follow-up questions come from.

More ways in: all 22 patterns, the curated study lists, or the full problem list.

What the depth-first search pattern is

When to use it

The depth-first search template in Python

Complexity characteristics

Meet the depth-first search problem you did not practise.

Approach

Approach

Approach

All 366 depth-first search LeetCode problems

Easy (41)41

Medium (214)214

Hard (111)111

Related patterns

Depth-First Search pattern FAQ

What is the depth-first search pattern?

How many LeetCode problems use the depth-first search pattern?

What is the time complexity of the depth-first search pattern?

When should I use the depth-first search pattern in an interview?

Which depth-first search problem should I start with?

What patterns are related to depth-first search?

Easy (41)

Medium (214)

Hard (111)