What is breadth-first tree traversal (BFS)?
Breadth-first traversal (BFS, Breadth-First Search) is a way of traversing a tree in which nodes are visited level by level, starting from the root and moving left to right at each level.
How it works
- Start at the root.
- Visit all nodes at the first level (the root's children).
- Then visit all nodes at the second level, then the third, and so on.
- A queue (FIFO) is used to keep track of the traversal order.
Step-by-step example
javascript
A
/ \
B C
/ \ \
D E FTraversal order:
A → B → C → D → E → F
The queue during traversal:
javascript
1. [A]
2. [B, C]
3. [C, D, E]
4. [D, E, F]
5. [E, F]
6. [F]
7. []Features of BFS
- Based on a queue.
- Good for finding the shortest path in unweighted graphs.
- Visits nodes layer by layer, not by depth.
Summary
BFS is a traversal that goes level by level from top to bottom, using a queue to remember the order of nodes, so that nodes close to the root are processed first, and deeper ones later.
Short Answer
Interview readyPremium
A concise answer to help you respond confidently on this topic during an interview.