Depth-First Search LeetCode Problems: All 289,
With Python Solutions

Every problem in this library that LeetCode tags Depth-First Search. 216 of them carry a complete Python solution, a worked example and the time and space complexity of the approach.

Get Stealth Interview

Easy: 39
Medium: 185
Hard: 65

1 pattern

How Depth-First Search problems are solved

A tag names the subject, not the method. These pattern hubs cover the techniques that actually solve Depth-First Search problems — each one explains the approach, gives a Python template and states its complexity.

Depth-First SearchFollow one path to its end before trying the next — the default way to explore a graph.

Eyes only

When the Depth-First Search problem arrives live.

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+

Depth-First Search problems by difficulty

Showing the first 200 of 289 problems. Problems with a complete Python solution are listed first, then by ascending problem number.

Easy (36)

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
0783	Minimum Distance Between BST Nodes	Tree, Depth-First Search, Breadth-First Search +2
0872	Leaf-Similar Trees	Tree, Depth-First Search, Binary Tree
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
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
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

Medium (127)

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
0785	Is Graph Bipartite?	Depth-First Search, Breadth-First Search, Union Find +1
0787	Cheapest Flights Within K Stops	Depth-First Search, Breadth-First Search, Graph +3
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
0841	Keys and Rooms	Depth-First Search, Breadth-First Search, Graph
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
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
1080	Insufficient Nodes in Root to Leaf Paths	Tree, Depth-First Search, Binary Tree
1110	Delete Nodes And Return Forest	Tree, Depth-First Search, Array +2
1123	Lowest Common Ancestor of Deepest Leaves	Tree, Depth-First Search, Breadth-First Search +2
1145	Binary Tree Coloring Game	Tree, Depth-First Search, Binary Tree
1161	Maximum Level Sum of a Binary Tree	Tree, Depth-First Search, Breadth-First Search +1
1202	Smallest String With Swaps	Depth-First Search, Breadth-First Search, Union Find +4
1233	Remove Sub-Folders from the Filesystem	Depth-First Search, Trie, Array +1
1254	Number of Closed Islands	Depth-First Search, Breadth-First Search, Union Find +2
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
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
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
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
1372	Longest ZigZag Path in a Binary Tree	Tree, Depth-First Search, Dynamic Programming +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
1443	Minimum Time to Collect All Apples in a Tree	Tree, Depth-First Search, Breadth-First Search +1
1448	Count Good Nodes in Binary 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
1466	Reorder Routes to Make All Paths Lead to the City Zero	Depth-First Search, Breadth-First Search, Graph
1519	Number of Nodes in the Sub-Tree With the Same Label	Tree, Depth-First Search, Breadth-First Search +2
1530	Number of Good Leaf Nodes Pairs	Tree, Depth-First Search, Binary Tree
1559	Detect Cycles in 2D Grid	Depth-First Search, Breadth-First Search, Union Find +2
1600	Throne Inheritance	Tree, Depth-First Search, Design +1
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
1722	Minimize Hamming Distance After Swap Operations	Depth-First Search, Union Find, Array
1743	Restore the Array From Adjacent Pairs	Depth-First Search, Array, Hash Table
1905	Count Sub Islands	Depth-First Search, Breadth-First Search, Union Find +2
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
2049	Count Nodes With the Highest Score	Tree, Depth-First Search, Array +1
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
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
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
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
2467	Most Profitable Path in a Tree	Tree, Depth-First Search, Breadth-First Search +2
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

Hard (37)

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
0753	Cracking the Safe	Depth-First Search, Graph, Eulerian Circuit
0765	Couples Holding Hands	Greedy, Depth-First Search, Breadth-First Search +2
0778	Swim in Rising Water	Depth-First Search, Breadth-First Search, Union Find +4
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
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
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
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
1568	Minimum Number of Days to Disconnect Island	Depth-First Search, Breadth-First Search, Array +2
1766	Tree of Coprimes	Tree, Depth-First Search, Array +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
2092	Find All People With Secret	Depth-First Search, Breadth-First Search, Union Find +2
2127	Maximum Employees to Be Invited to a Meeting	Depth-First Search, Graph, Topological Sort
2246	Longest Path With Different Adjacent Characters	Tree, Depth-First Search, Graph +3
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
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

How Depth-First Search problems are solved

When the Depth-First Search problem arrives live.

Approach

Approach

Approach

Depth-First Search problems by difficulty

Easy (36)36

Medium (127)127

Hard (37)37

Keep exploring

Easy (36)

Medium (127)

Hard (37)