Last Minute Notes
  • Github
  • Docs
  • Learn
    @sayanstwt
Lessons
0/15 done
  • Tree BFS
  • Tree DFS
  • Two Heaps
  • Top K Elements
  • K-way Merge
  • Trie
Learn/Data Structures & Algorithms/Trees & Heaps

Tree BFS

7 min Beginner 8 steps

Visit a tree level by level with a queue.

Nodes
5
Levels
3
Output rows
3
3920157WANTemptyreturn the values row by row
current visited done
In this lessonStep 1 of 8
  1. The problem
  2. Levels
  3. Full run
  4. Right view
  5. Min depth
  6. Memory
  7. Multi-source
  8. Recap
Step 1 / 8problem

Answer the tree row by row

Return the values of [3, 9, 20, null, null, 15, 7] grouped by level: [[3], [9, 20], [15, 7]].

Nodes only point to their children. Nothing tells you which row a node sits on, so the traversal has to keep the rows apart.

Key idea

Level order, "by row", "depth k", side views, minimum depth, and unweighted shortest paths all point to BFS.

←→ step·R replay·Space pause

You'll learn

  • Recognise "by level" problems that want BFS
  • Run the level-array template without shift()
  • Adapt it for right side view and minimum depth
  • Use multi-source BFS for "distance to nearest X"
Read the full notesTrees, Graphs and Search, 2