Depth-First Search LeetCode Problems: All 289, With Python Solutions
Every problem in this library that LeetCode tags Depth-First Search — 289 in total, 216 of them with a complete Python solution, a worked example and the time and space complexity of the approach.
- 289 problems
- 39 Easy
- 185 Medium
- 65 Hard
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 Search — Follow one path to its end before trying the next — the default way to explore a graph.
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)
| # | Problem | Difficulty | Topics |
|---|---|---|---|
| 94 | Binary Tree Inorder Traversal | Easy | Stack, Tree, Depth-First Search +1 |
| 100 | Same Tree | Easy | Tree, Depth-First Search, Breadth-First Search +1 |
| 101 | Symmetric Tree | Easy | Tree, Depth-First Search, Breadth-First Search +1 |
| 104 | Maximum Depth of Binary Tree | Easy | Tree, Depth-First Search, Breadth-First Search +1 |
| 110 | Balanced Binary Tree | Easy | Tree, Depth-First Search, Binary Tree |
| 111 | Minimum Depth of Binary Tree | Easy | Tree, Depth-First Search, Breadth-First Search +1 |
| 112 | Path Sum | Easy | Tree, Depth-First Search, Breadth-First Search +1 |
| 144 | Binary Tree Preorder Traversal | Easy | Stack, Tree, Depth-First Search +1 |
| 145 | Binary Tree Postorder Traversal | Easy | Stack, Tree, Depth-First Search +1 |
| 226 | Invert Binary Tree | Easy | Tree, Depth-First Search, Breadth-First Search +1 |
| 257 | Binary Tree Paths | Easy | Tree, Depth-First Search, String +2 |
| 404 | Sum of Left Leaves | Easy | Tree, Depth-First Search, Breadth-First Search +1 |
| 463 | Island Perimeter | Easy | Depth-First Search, Breadth-First Search, Array +1 |
| 501 | Find Mode in Binary Search Tree | Easy | Tree, Depth-First Search, Binary Search Tree +1 |
| 530 | Minimum Absolute Difference in BST | Easy | Tree, Depth-First Search, Breadth-First Search +2 |
| 543 | Diameter of Binary Tree | Easy | Tree, Depth-First Search, Binary Tree |
| 559 | Maximum Depth of N-ary Tree | Easy | Tree, Depth-First Search, Breadth-First Search |
| 563 | Binary Tree Tilt | Easy | Tree, Depth-First Search, Binary Tree |
| 572 | Subtree of Another Tree | Easy | Tree, Depth-First Search, Binary Tree +2 |
| 589 | N-ary Tree Preorder Traversal | Easy | Stack, Tree, Depth-First Search |
| 590 | N-ary Tree Postorder Traversal | Easy | Stack, Tree, Depth-First Search |
| 617 | Merge Two Binary Trees | Easy | Tree, Depth-First Search, Breadth-First Search +1 |
| 637 | Average of Levels in Binary Tree | Easy | Tree, Depth-First Search, Breadth-First Search +1 |
| 653 | Two Sum IV - Input is a BST | Easy | Tree, Depth-First Search, Breadth-First Search +4 |
| 671 | Second Minimum Node In a Binary Tree | Easy | Tree, Depth-First Search, Binary Tree |
| 733 | Flood Fill | Easy | Depth-First Search, Breadth-First Search, Array +1 |
| 783 | Minimum Distance Between BST Nodes | Easy | Tree, Depth-First Search, Breadth-First Search +2 |
| 872 | Leaf-Similar Trees | Easy | Tree, Depth-First Search, Binary Tree |
| 897 | Increasing Order Search Tree | Easy | Stack, Tree, Depth-First Search +2 |
| 938 | Range Sum of BST | Easy | Tree, Depth-First Search, Binary Search Tree +1 |
| 965 | Univalued Binary Tree | Easy | Tree, Depth-First Search, Breadth-First Search +1 |
| 993 | Cousins in Binary Tree | Easy | Tree, Depth-First Search, Breadth-First Search +1 |
| 1022 | Sum of Root To Leaf Binary Numbers | Easy | Tree, Depth-First Search, Binary Tree |
| 1379 | Find a Corresponding Node of a Binary Tree in a Clone of That Tree | Easy | Tree, Depth-First Search, Breadth-First Search +1 |
| 1971 | Find if Path Exists in Graph | Easy | Depth-First Search, Breadth-First Search, Union Find +1 |
| 2331 | Evaluate Boolean Binary Tree | Easy | Tree, Depth-First Search, Binary Tree |
Medium (127)
| # | Problem | Difficulty | Topics |
|---|---|---|---|
| 79 | Word Search | Medium | Depth-First Search, Array, String +2 |
| 98 | Validate Binary Search Tree | Medium | Tree, Depth-First Search, Binary Search Tree +1 |
| 99 | Recover Binary Search Tree | Medium | Tree, Depth-First Search, Binary Search Tree +1 |
| 113 | Path Sum II | Medium | Tree, Depth-First Search, Backtracking +1 |
| 114 | Flatten Binary Tree to Linked List | Medium | Stack, Tree, Depth-First Search +2 |
| 116 | Populating Next Right Pointers in Each Node | Medium | Tree, Depth-First Search, Breadth-First Search +2 |
| 117 | Populating Next Right Pointers in Each Node II | Medium | Tree, Depth-First Search, Breadth-First Search +2 |
| 129 | Sum Root to Leaf Numbers | Medium | Tree, Depth-First Search, Binary Tree |
| 130 | Surrounded Regions | Medium | Depth-First Search, Breadth-First Search, Union Find +2 |
| 133 | Clone Graph | Medium | Depth-First Search, Breadth-First Search, Graph +1 |
| 199 | Binary Tree Right Side View | Medium | Tree, Depth-First Search, Breadth-First Search +1 |
| 200 | Number of Islands | Medium | Depth-First Search, Breadth-First Search, Union Find +2 |
| 207 | Course Schedule | Medium | Depth-First Search, Breadth-First Search, Graph +1 |
| 210 | Course Schedule II | Medium | Depth-First Search, Breadth-First Search, Graph +1 |
| 211 | Design Add and Search Words Data Structure | Medium | Depth-First Search, Design, Trie +1 |
| 230 | Kth Smallest Element in a BST | Medium | Tree, Depth-First Search, Binary Search Tree +1 |
| 235 | Lowest Common Ancestor of a Binary Search Tree | Medium | Tree, Depth-First Search, Binary Search Tree +1 |
| 236 | Lowest Common Ancestor of a Binary Tree | Medium | Tree, Depth-First Search, Binary Tree |
| 310 | Minimum Height Trees | Medium | Depth-First Search, Breadth-First Search, Graph +1 |
| 337 | House Robber III | Medium | Tree, Depth-First Search, Dynamic Programming +1 |
| 341 | Flatten Nested List Iterator | Medium | Stack, Tree, Depth-First Search +3 |
| 365 | Water and Jug Problem | Medium | Depth-First Search, Breadth-First Search, Math |
| 385 | Mini Parser | Medium | Stack, Depth-First Search, String |
| 386 | Lexicographical Numbers | Medium | Depth-First Search, Trie |
| 388 | Longest Absolute File Path | Medium | Stack, Depth-First Search, String |
| 399 | Evaluate Division | Medium | Depth-First Search, Breadth-First Search, Union Find +4 |
| 417 | Pacific Atlantic Water Flow | Medium | Depth-First Search, Breadth-First Search, Array +1 |
| 419 | Battleships in a Board | Medium | Depth-First Search, Array, Matrix |
| 430 | Flatten a Multilevel Doubly Linked List | Medium | Depth-First Search, Linked List, Doubly-Linked List |
| 437 | Path Sum III | Medium | Tree, Depth-First Search, Binary Tree |
| 449 | Serialize and Deserialize BST | Medium | Tree, Depth-First Search, Breadth-First Search +4 |
| 508 | Most Frequent Subtree Sum | Medium | Tree, Depth-First Search, Hash Table +1 |
| 513 | Find Bottom Left Tree Value | Medium | Tree, Depth-First Search, Breadth-First Search +1 |
| 515 | Find Largest Value in Each Tree Row | Medium | Tree, Depth-First Search, Breadth-First Search +1 |
| 529 | Minesweeper | Medium | Depth-First Search, Breadth-First Search, Array +1 |
| 538 | Convert BST to Greater Tree | Medium | Tree, Depth-First Search, Binary Search Tree +1 |
| 547 | Number of Provinces | Medium | Depth-First Search, Breadth-First Search, Union Find +1 |
| 565 | Array Nesting | Medium | Depth-First Search, Array |
| 606 | Construct String from Binary Tree | Medium | Tree, Depth-First Search, String +1 |
| 623 | Add One Row to Tree | Medium | Tree, Depth-First Search, Breadth-First Search +1 |
| 652 | Find Duplicate Subtrees | Medium | Tree, Depth-First Search, Hash Table +1 |
| 655 | Print Binary Tree | Medium | Tree, Depth-First Search, Breadth-First Search +1 |
| 662 | Maximum Width of Binary Tree | Medium | Tree, Depth-First Search, Breadth-First Search +1 |
| 669 | Trim a Binary Search Tree | Medium | Tree, Depth-First Search, Binary Search Tree +1 |
| 672 | Bulb Switcher II | Medium | Bit Manipulation, Depth-First Search, Breadth-First Search +1 |
| 676 | Implement Magic Dictionary | Medium | Depth-First Search, Design, Trie +2 |
| 684 | Redundant Connection | Medium | Depth-First Search, Breadth-First Search, Union Find +1 |
| 687 | Longest Univalue Path | Medium | Tree, Depth-First Search, Binary Tree |
| 690 | Employee Importance | Medium | Tree, Depth-First Search, Breadth-First Search +2 |
| 695 | Max Area of Island | Medium | Depth-First Search, Breadth-First Search, Union Find +2 |
| 721 | Accounts Merge | Medium | Depth-First Search, Breadth-First Search, Union Find +4 |
| 743 | Network Delay Time | Medium | Depth-First Search, Breadth-First Search, Graph +2 |
| 785 | Is Graph Bipartite? | Medium | Depth-First Search, Breadth-First Search, Union Find +1 |
| 787 | Cheapest Flights Within K Stops | Medium | Depth-First Search, Breadth-First Search, Graph +3 |
| 797 | All Paths From Source to Target | Medium | Depth-First Search, Breadth-First Search, Graph +1 |
| 802 | Find Eventual Safe States | Medium | Depth-First Search, Breadth-First Search, Graph +1 |
| 814 | Binary Tree Pruning | Medium | Tree, Depth-First Search, Binary Tree |
| 841 | Keys and Rooms | Medium | Depth-First Search, Breadth-First Search, Graph |
| 851 | Loud and Rich | Medium | Depth-First Search, Graph, Topological Sort +1 |
| 863 | All Nodes Distance K in Binary Tree | Medium | Tree, Depth-First Search, Breadth-First Search +2 |
| 865 | Smallest Subtree with all the Deepest Nodes | Medium | Tree, Depth-First Search, Breadth-First Search +2 |
| 886 | Possible Bipartition | Medium | Depth-First Search, Breadth-First Search, Union Find +1 |
| 934 | Shortest Bridge | Medium | Depth-First Search, Breadth-First Search, Array +1 |
| 947 | Most Stones Removed with Same Row or Column | Medium | Depth-First Search, Union Find, Graph +1 |
| 951 | Flip Equivalent Binary Trees | Medium | Tree, Depth-First Search, Binary Tree |
| 959 | Regions Cut By Slashes | Medium | Depth-First Search, Breadth-First Search, Union Find +3 |
| 971 | Flip Binary Tree To Match Preorder Traversal | Medium | Tree, Depth-First Search, Binary Tree |
| 979 | Distribute Coins in Binary Tree | Medium | Tree, Depth-First Search, Binary Tree |
| 988 | Smallest String Starting From Leaf | Medium | Tree, Depth-First Search, String +2 |
| 1020 | Number of Enclaves | Medium | Depth-First Search, Breadth-First Search, Union Find +2 |
| 1026 | Maximum Difference Between Node and Ancestor | Medium | Tree, Depth-First Search, Binary Tree |
| 1034 | Coloring A Border | Medium | Depth-First Search, Breadth-First Search, Array +1 |
| 1038 | Binary Search Tree to Greater Sum Tree | Medium | Tree, Depth-First Search, Binary Search Tree +1 |
| 1042 | Flower Planting With No Adjacent | Medium | Depth-First Search, Breadth-First Search, Graph |
| 1080 | Insufficient Nodes in Root to Leaf Paths | Medium | Tree, Depth-First Search, Binary Tree |
| 1110 | Delete Nodes And Return Forest | Medium | Tree, Depth-First Search, Array +2 |
| 1123 | Lowest Common Ancestor of Deepest Leaves | Medium | Tree, Depth-First Search, Breadth-First Search +2 |
| 1145 | Binary Tree Coloring Game | Medium | Tree, Depth-First Search, Binary Tree |
| 1161 | Maximum Level Sum of a Binary Tree | Medium | Tree, Depth-First Search, Breadth-First Search +1 |
| 1202 | Smallest String With Swaps | Medium | Depth-First Search, Breadth-First Search, Union Find +4 |
| 1233 | Remove Sub-Folders from the Filesystem | Medium | Depth-First Search, Trie, Array +1 |
| 1254 | Number of Closed Islands | Medium | Depth-First Search, Breadth-First Search, Union Find +2 |
| 1261 | Find Elements in a Contaminated Binary Tree | Medium | Tree, Depth-First Search, Breadth-First Search +3 |
| 1267 | Count Servers that Communicate | Medium | Depth-First Search, Breadth-First Search, Union Find +3 |
| 1302 | Deepest Leaves Sum | Medium | Tree, Depth-First Search, Breadth-First Search +1 |
| 1305 | All Elements in Two Binary Search Trees | Medium | Tree, Depth-First Search, Binary Search Tree +2 |
| 1306 | Jump Game III | Medium | Depth-First Search, Breadth-First Search, Array |
| 1315 | Sum of Nodes with Even-Valued Grandparent | Medium | Tree, Depth-First Search, Breadth-First Search +1 |
| 1319 | Number of Operations to Make Network Connected | Medium | Depth-First Search, Breadth-First Search, Union Find +1 |
| 1325 | Delete Leaves With a Given Value | Medium | Tree, Depth-First Search, Binary Tree |
| 1339 | Maximum Product of Splitted Binary Tree | Medium | Tree, Depth-First Search, Binary Tree |
| 1361 | Validate Binary Tree Nodes | Medium | Tree, Depth-First Search, Breadth-First Search +3 |
| 1367 | Linked List in Binary Tree | Medium | Tree, Depth-First Search, Linked List +1 |
| 1372 | Longest ZigZag Path in a Binary Tree | Medium | Tree, Depth-First Search, Dynamic Programming +1 |
| 1376 | Time Needed to Inform All Employees | Medium | Tree, Depth-First Search, Breadth-First Search |
| 1382 | Balance a Binary Search Tree | Medium | Greedy, Tree, Depth-First Search +3 |
| 1391 | Check if There is a Valid Path in a Grid | Medium | Depth-First Search, Breadth-First Search, Union Find +2 |
| 1443 | Minimum Time to Collect All Apples in a Tree | Medium | Tree, Depth-First Search, Breadth-First Search +1 |
| 1448 | Count Good Nodes in Binary Tree | Medium | Tree, Depth-First Search, Breadth-First Search +1 |
| 1457 | Pseudo-Palindromic Paths in a Binary Tree | Medium | Bit Manipulation, Tree, Depth-First Search +2 |
| 1462 | Course Schedule IV | Medium | Depth-First Search, Breadth-First Search, Graph +1 |
| 1466 | Reorder Routes to Make All Paths Lead to the City Zero | Medium | Depth-First Search, Breadth-First Search, Graph |
| 1519 | Number of Nodes in the Sub-Tree With the Same Label | Medium | Tree, Depth-First Search, Breadth-First Search +2 |
| 1530 | Number of Good Leaf Nodes Pairs | Medium | Tree, Depth-First Search, Binary Tree |
| 1559 | Detect Cycles in 2D Grid | Medium | Depth-First Search, Breadth-First Search, Union Find +2 |
| 1600 | Throne Inheritance | Medium | Tree, Depth-First Search, Design +1 |
| 1625 | Lexicographically Smallest String After Applying Operations | Medium | Depth-First Search, Breadth-First Search, String +1 |
| 1631 | Path With Minimum Effort | Medium | Depth-First Search, Breadth-First Search, Union Find +4 |
| 1722 | Minimize Hamming Distance After Swap Operations | Medium | Depth-First Search, Union Find, Array |
| 1743 | Restore the Array From Adjacent Pairs | Medium | Depth-First Search, Array, Hash Table |
| 1905 | Count Sub Islands | Medium | Depth-First Search, Breadth-First Search, Union Find +2 |
| 1992 | Find All Groups of Farmland | Medium | Depth-First Search, Breadth-First Search, Array +1 |
| 1993 | Operations on Tree | Medium | Tree, Depth-First Search, Breadth-First Search +3 |
| 2049 | Count Nodes With the Highest Score | Medium | Tree, Depth-First Search, Array +1 |
| 2096 | Step-By-Step Directions From a Binary Tree Node to Another | Medium | Tree, Depth-First Search, String +1 |
| 2101 | Detonate the Maximum Bombs | Medium | Depth-First Search, Breadth-First Search, Graph +3 |
| 2192 | All Ancestors of a Node in a Directed Acyclic Graph | Medium | Depth-First Search, Breadth-First Search, Graph +1 |
| 2265 | Count Nodes Equal to Average of Subtree | Medium | Tree, Depth-First Search, Binary Tree |
| 2316 | Count Unreachable Pairs of Nodes in an Undirected Graph | Medium | Depth-First Search, Breadth-First Search, Union Find +1 |
| 2359 | Find Closest Node to Given Two Nodes | Medium | Depth-First Search, Graph |
| 2368 | Reachable Nodes With Restrictions | Medium | Tree, Depth-First Search, Breadth-First Search +4 |
| 2385 | Amount of Time for Binary Tree to Be Infected | Medium | Tree, Depth-First Search, Breadth-First Search +2 |
| 2415 | Reverse Odd Levels of Binary Tree | Medium | Tree, Depth-First Search, Breadth-First Search +1 |
| 2467 | Most Profitable Path in a Tree | Medium | Tree, Depth-First Search, Breadth-First Search +2 |
| 2476 | Closest Nodes Queries in a Binary Search Tree | Medium | Tree, Depth-First Search, Binary Search Tree +3 |
| 2477 | Minimum Fuel Cost to Report to the Capital | Medium | Tree, Depth-First Search, Breadth-First Search +1 |
| 2492 | Minimum Score of a Path Between Two Cities | Medium | Depth-First Search, Breadth-First Search, Union Find +1 |
Hard (37)
| # | Problem | Difficulty | Topics |
|---|---|---|---|
| 124 | Binary Tree Maximum Path Sum | Hard | Tree, Depth-First Search, Dynamic Programming +1 |
| 297 | Serialize and Deserialize Binary Tree | Hard | Tree, Depth-First Search, Breadth-First Search +3 |
| 329 | Longest Increasing Path in a Matrix | Hard | Depth-First Search, Breadth-First Search, Graph +5 |
| 332 | Reconstruct Itinerary | Hard | Depth-First Search, Graph, Eulerian Circuit |
| 472 | Concatenated Words | Hard | Depth-First Search, Trie, Array +3 |
| 514 | Freedom Trail | Hard | Depth-First Search, Breadth-First Search, String +1 |
| 685 | Redundant Connection II | Hard | Depth-First Search, Breadth-First Search, Union Find +1 |
| 749 | Contain Virus | Hard | Depth-First Search, Breadth-First Search, Array +2 |
| 753 | Cracking the Safe | Hard | Depth-First Search, Graph, Eulerian Circuit |
| 765 | Couples Holding Hands | Hard | Greedy, Depth-First Search, Breadth-First Search +2 |
| 778 | Swim in Rising Water | Hard | Depth-First Search, Breadth-First Search, Union Find +4 |
| 827 | Making A Large Island | Hard | Depth-First Search, Breadth-First Search, Union Find +2 |
| 834 | Sum of Distances in Tree | Hard | Tree, Depth-First Search, Graph +1 |
| 839 | Similar String Groups | Hard | Depth-First Search, Breadth-First Search, Union Find +3 |
| 924 | Minimize Malware Spread | Hard | Depth-First Search, Breadth-First Search, Union Find +3 |
| 928 | Minimize Malware Spread II | Hard | Depth-First Search, Breadth-First Search, Union Find +3 |
| 968 | Binary Tree Cameras | Hard | Tree, Depth-First Search, Dynamic Programming +1 |
| 987 | Vertical Order Traversal of a Binary Tree | Hard | Tree, Depth-First Search, Breadth-First Search +3 |
| 1028 | Recover a Tree From Preorder Traversal | Hard | Tree, Depth-First Search, String +1 |
| 1036 | Escape a Large Maze | Hard | Depth-First Search, Breadth-First Search, Array +1 |
| 1192 | Critical Connections in a Network | Hard | Depth-First Search, Graph, Biconnected Component |
| 1203 | Sort Items by Groups Respecting Dependencies | Hard | Depth-First Search, Breadth-First Search, Graph +1 |
| 1373 | Maximum Sum BST in Binary Tree | Hard | Tree, Depth-First Search, Binary Search Tree +2 |
| 1377 | Frog Position After T Seconds | Hard | Tree, Depth-First Search, Breadth-First Search +1 |
| 1483 | Kth Ancestor of a Tree Node | Hard | Bit Manipulation, Tree, Depth-First Search +4 |
| 1568 | Minimum Number of Days to Disconnect Island | Hard | Depth-First Search, Breadth-First Search, Array +2 |
| 1766 | Tree of Coprimes | Hard | Tree, Depth-First Search, Array +2 |
| 1970 | Last Day Where You Can Still Cross | Hard | Depth-First Search, Breadth-First Search, Union Find +3 |
| 2003 | Smallest Missing Genetic Value in Each Subtree | Hard | Tree, Depth-First Search, Union Find +1 |
| 2092 | Find All People With Secret | Hard | Depth-First Search, Breadth-First Search, Union Find +2 |
| 2127 | Maximum Employees to Be Invited to a Meeting | Hard | Depth-First Search, Graph, Topological Sort |
| 2246 | Longest Path With Different Adjacent Characters | Hard | Tree, Depth-First Search, Graph +3 |
| 2322 | Minimum Score After Removals on a Tree | Hard | Bit Manipulation, Tree, Depth-First Search +1 |
| 2328 | Number of Increasing Paths in a Grid | Hard | Depth-First Search, Breadth-First Search, Graph +5 |
| 2360 | Longest Cycle in a Graph | Hard | Depth-First Search, Breadth-First Search, Graph +1 |
| 2440 | Create Components With Same Value | Hard | Tree, Depth-First Search, Array +2 |
| 2458 | Height of Binary Tree After Subtree Removal Queries | Hard | Tree, Depth-First Search, Breadth-First Search +2 |
Keep exploring
All LeetCode topicsEvery tag with a page of its own, with the number of problems behind each.LeetCode patternsThe techniques themselves, with a Python template and complexity for each.Curated study listsBlind 75, NeetCode 150 and three more, grouped by pattern.Easy problemsStart here when the data structure is new rather than the problem.
Other topics
- Array1,569
- String672
- Hash Table588
- Math485
- Dynamic Programming481
- Sorting392
- Greedy346
- Binary Search253
- Database249
- Tree225
- Breadth-First Search223
- Matrix216
- Two Pointers201
- Bit Manipulation194
- Binary Tree174
- Heap (Priority Queue)163
- Prefix Sum157
- Stack157
- Simulation144
- Graph138
- Counting126
- Design122
- Sliding Window116
- Backtracking105
When the Depth-First Search problem arrives live
Stealth Interview is a desktop app for macOS and Windows. It reads the coding 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 is saying — while staying invisible to screen sharing.