Depth-First Search (DFS) and Depth-First Traversal
Depth-first search (DFS) is a method for exploring a
tree or graph. In a DFS, you go as deep as possible down one path
before backing up and trying a different one.
Depth-first search is like walking through a corn maze. You explore
one path, hit a dead end, and go back and try a different one.
Here's a how a DFS would traverse this tree, starting with the root:
We'd go down the first path we find until we hit a dead end:
Then we'd do the same thing again—go down a path until we hit a dead end:
Until we reach the end.
Depth-first search is often compared with breadth-first search.
Depth-first search on a binary tree generally requires
less memory than breadth-first.
Depth-first search can be easily implemented with recursion.
A DFS doesn't necessarily find the shortest path to a node, while
breadth-first search does.
Interview coming up?
Get the free 7-day email crash course. You'll learn how to think algorithmically, so you can break down tricky coding interview
No prior computer science training necessary—we'll get you up to speed quickly, skipping all the
overly academic stuff.
No spam. One-click unsubscribe whenever.
You're in! Head over to your email inbox right now to read day one!
Log in/sign up
With just a couple clicks.
We'll never post on your wall or message your friends.
Where do I enter my password?
Actually, we don't support password-based login. Never have. Just the OAuth methods above. Why?
It's easy and quick. No "reset password" flow. No password to forget.
It lets us avoid storing passwords that hackers could access and use to try to log into our users' email or bank accounts.
It makes it harder for one person to share a paid Interview Cake account with multiple people.
“I had my non-technical friend use Interview Cake as a script and mock interview me. It worked perfectly. Super easy to follow. Thanks!
. . .