TRT
Sign in

Advanced · Module 13 · Lesson 3 of 5

Depth-first search

Depth-first search follows one path as far as it can, then backs up and tries the next. It is the natural way to flood a region, explore every possibility, or ask what is reachable, as long as you watch its depth.

Pro — members onlyAbout 14 minutes

By the end you can

  • Run depth-first search recursively and with an explicit stack
  • Flood-fill regions of a grid and count connected regions
  • Choose between DFS and BFS, and avoid stack overflow on deep searches

Builds on Breadth-first search.

01 · A question first

How many islands are on a map of land and water? Each time you step onto land you haven't seen, flood outward until no land is left, and you have found one whole island. Which order of exploration makes that flood the simplest to write?

Make a guess before you read on.

02 · The idea

Members only

Unlock the full lesson

This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.

What's inside

  • Deep before wide
  • Flood fill
  • The explicit stack
  • Which search?
  • Recursive and iterative orders differ
  • Timestamps
  • What DFS knows that BFS doesn't
  • Pseudocode & Multi-Language Implementations (C++, Java, Python)
See plansAlready a member? Sign in

03 · Practice

Practice · medium · LeetCodeNumber of islandsCount the islands in a grid of land and water, flooding each one with DFS or BFS the first time you step on it.Practice · medium · LeetCodeMax area of islandFind the largest island in a grid by having each flood fill return the number of cells it marked.Practice · medium · LeetCodePacific Atlantic water flowFind the cells whose water can reach both oceans by searching uphill from each ocean's border and intersecting the results.Practice · hard · LeetCodeReconstruct itineraryUse every flight ticket exactly once, starting from JFK and preferring alphabetical order, with a DFS that adds airports after their tickets run out.

Asked in interviews

Something wrong with this lesson? Report a problem