BFS on Trees
Use a queue to visit the tree level by level instead of going deep first.
0 of 3 problems solved
BFS on Trees
Use a queue to visit the tree level by level instead of going deep first.
- •Do I need to visit nodes level by level instead of deep first?
- •Would a queue make the order natural?
- •Can I process one level at a time by using the queue size?
Breadth First Search visits a tree level by level instead of diving deep. A queue is perfect for that because the first node discovered is the first node processed. So BFS feels like a line at a ticket counter: whoever arrives first gets served first, and each level waits its turn.
If the problem talks about levels, a queue should start ringing in your head immediately.
- 1Start by putting the root in a queue.
- 2While the queue is not empty, process exactly one level at a time.
- 3Pop nodes from the front and record their values.
- 4Push their children to the back for the next level.
If you do not measure the current queue size before processing a level, you can accidentally mix multiple levels together.
Minimum Depth of Binary Tree
DFS but return 1 + min(left, right) only when both children exist. A node with only one child must route depth through that child.
Word Ladder
BFS on words where each edge is one character change. Track unused words in a Set and shrink it as you visit. Level count at the target is the answer.