Medium · Breadth-First Search
Understand → Visualise → Practice.
Depth-first search dives down one branch. Breadth-first search explores the tree one level at a time.
Use a queue. At the start of each level, the queue holds exactly that level's nodes; remove them and add their children.
queue = [root].
size = len(queue) before you start the level.
Record their values; enqueue their children.
O(n) time. O(w) space, where w is the widest level.
Read the queue length before the loop; it changes as children are added.
Read the full guides first: Binary Trees and Traversals, Binary Search Trees, Graphs, BFS and DFS, Weighted Graphs, Dijkstra and Union–Find.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.