Breadth-First Search (BFS) and Breadth-First Traversal
Breadth-first search (BFS) is a method for
exploring a tree or graph. In a BFS, you first explore all the
nodes one step away, then all the nodes two steps away, etc.
Breadth-first search is like throwing a stone in the center of a
pond. The nodes you explore "ripple out" from the starting point.
Here's a how a BFS would traverse this tree, starting with the root:
We'd visit all the immediate children (all the nodes that're one step away from our starting node):
Then we'd move on to all those nodes' children (all the nodes that're two steps away from our starting node):
And so on:
Until we reach the end.
Breadth-first search is often compared with depth-first search.
A BFS will find the shortest path between the
starting point and any other reachable node. A depth-first search
will not necessarily find the shortest path.
A BFS on a binary tree generally requires more memory than a DFS.
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.
“Interview Cake helped me so much when I needed to accelerate my learning for interviews. If you need something to use as a study guide, check it out :D
. . .