cf.completefrontend
TREES & TRIES · FOUNDATION

Level-order traversal (tree BFS)

Visit a tree one level at a time, from the root down, using a queue of the nodes waiting to be visited.

Time O(n)Space O(w)6 practice problemsStep-through picture

The idea

Sometimes you care about rows, not branches: all the nodes 1 step from the root, then all the nodes 2 steps away, and so on. The number of steps from the root is a node's depth, and all nodes with the same depth form a level.

Level-order traversal visits the root, then its children, then its grandchildren. It is also called breadth-first search, or BFS, because it covers the whole width of one level before going deeper.

The trick is to keep the nodes of the current level in a list called queue. While you visit them, you collect their children into a second list called next. When the current level is done, next becomes the new queue. A queue is a line where the first one in is the first one out.

An everyday example

Passing news down a family tree

A grandmother tells her news to her children on Monday. On Tuesday each of them tells their own children. On Wednesday those children tell theirs. Everyone who hears the news on the same day is in the same generation. You can write down each day's list of people, and you never hear about a great-grandchild before a grandchild.

How the example maps to the code
In the exampleIn the code
The people hearing the news todayqueue
The people they will tell tomorrownext
Writing down today's nameslevel.push(node.val)
The next day startsqueue = next

From the slow way to level-order traversal (tree bfs)

  1. Suppose you need a tree's values row by row. One slow way: for each depth 0, 1, 2, and so on, walk the whole tree with DFS and collect only the nodes at that depth. With h levels that's h full walks, O(n · h) work, which is O(n²) for a tree shaped like a chain.
  2. The waste is easy to see. While you are looking at the nodes of one level, you are already holding the only nodes whose children can form the next level. Nothing else in the tree can be one level deeper. So instead of searching for level d + 1 from scratch, read it off the nodes of level d.
  3. Keep the current level in a list, queue. Visit its nodes from left to right, record their values in level, and put their children, left before right, into a second list, next. When queue is used up, next holds the whole next level, already in left-to-right order.
  4. Then swap with queue = next and repeat until a level has no children at all. Each node is touched once, when its parent's level is handled. That loop, one level at a time with a list of waiting nodes, is level-order traversal, also called breadth-first search.

How it works

  1. If the tree is empty, return an empty list. Otherwise put the root in queue.
  2. While queue has nodes, start a new level list and an empty next list.
  3. For each node in queue, add node.val to level.
  4. Add node.left and then node.right to next, skipping missing children.
  5. When every node in queue is done, push level onto levels.
  6. Set queue = next and repeat. When a level has no children, next is empty and the loop ends.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function levelOrder(root) {
  2. const levels = [];
  3. if (root === null) return levels;
  4. let queue = [root];
  5. while (queue.length > 0) {
  6. const level = [];
  7. const next = [];
  8. for (const node of queue) {
  9. level.push(node.val);
  10. if (node.left) next.push(node.left);
  11. if (node.right) next.push(node.right);
  12. }
  13. levels.push(level);
  14. queue = next;
  15. }
  16. return levels;
  17. }

How fast it is

TimeO(n)
Extra memoryO(w)

Each node is added and read once. The lists hold at most two levels at a time, so memory grows with the widest level w, which can be about n / 2 in a full tree.

  • Best caseO(n)

    Any tree, even a chain of n nodes, which takes n rounds of one node each. A full listing can't skip any node.

  • Average caseO(n)

    A random tree: each node is pushed into next once and read once.

  • Worst caseO(n)

    A perfect tree of 1,023 nodes. It's still 1,023 visits, but the last level alone holds 512 nodes, the most memory this walk can need.

Common mistakes

  • Using one array and pushing children into the same list you are looping over. The loop then runs into the next level, and the levels mix. Keep next separate, or record the level size before the loop.
  • Pushing null children into the queue and then reading node.val of null. Check the child before pushing it.
  • Adding the right child before the left one. The levels then come out right-to-left, which is wrong unless the problem asks for that.
  • Using queue.shift() on large inputs, which can make the walk quadratic. Swap lists or use a head index.

When to use it

Look for these clues in a problem:

  • The question says "level", "row", "generation", "depth by depth", or "layer".
  • You need something per level: the rightmost node, the average, the widest row.
  • You want the shallowest node that matches something, like the nearest leaf. BFS finds it first.
  • The output is a list of lists, one inner list per level.

Check yourself

Answer each one in your head first, then open it.

Why must next be a separate list from queue?

If you pushed children onto the list you're looping over, the for loop would keep going into them, and the next level would be mixed into this one.

How many rounds of the while loop run on a tree with 5 levels?

Five, one per level. The fifth round leaves next empty, so the loop stops.

Which uses less memory on a perfect tree of 1,023 nodes, BFS or DFS?

DFS. Its stack holds one path, about 10 calls, while BFS holds up to the whole bottom level of 512 nodes.

What changes if you add node.right before node.left?

Every row comes out right to left. Each row still has the right set of nodes; only the order inside each row flips.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 6 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The rule at the top of each while round: queue holds every node at depth d, in left-to-right order, and nothing else. At the start, d = 0 and queue = [root], which is the whole of level 0, so the rule holds.

Each round keeps it. Every node at depth d + 1 has exactly one parent, and that parent is at depth d, so it's in queue. The for loop visits each parent once and adds its children, so every node of level d + 1 lands in next exactly once. Parents are visited left to right and each one adds its left child before its right child, so next is in left-to-right order too.

The loop ends because the tree has a finite height: once d passes the deepest level, next is empty. Each round records exactly one complete level in order, so when the loop stops, levels lists every level from the top down.

Going deeper

3 more ideas

Why the levels never mix

At the start of each loop, queue holds exactly the nodes of one level, from left to right. Their children are all one level deeper, and they go into a separate list, next. Because we only swap the lists when the whole level is done, a deeper node can never be visited before a shallower one.

Time and memory

Each node enters next once and is read once, so the time is O(n). The memory is the widest level, because queue and next together hold at most two levels. In a full tree the last level holds about half of all nodes, so the worst case is O(n).

Why not queue.shift()

Many examples use one array and queue.shift() to take the front item. In JavaScript, shift() moves every other item one step left, so it can cost O(n) each time and the whole walk becomes O(n^2) on wide trees. Swapping in a fresh next list, or reading with a moving head index, keeps each step O(1).

Work it by hand

Every step in a table, with why

List a 7-node tree level by level. One node has only a left child and another has only a right child, so the trace shows both skips.

root = [10, 6, 15, 2, null, 12, 20, null, 4] (`6` has left child `2`, `2` has right child `4`)

StepqueuenodelevelnextWhat happensWhy
1[10]10[10][6, 15]both children addedLevel 0 holds only the root. Its two children go into next, left first.
2[10]-[10][6, 15]save level, queue = nextThe for loop is done. levels becomes [[10]], and the two children become the new queue.
3[6, 15]6[6][2]only a left child6 has a left child 2 and no right child, so only 2 is added.
4[6, 15]15[6, 15][2, 12, 20]both children added15 adds 12 and then 20, after 2, so next stays in left-to-right order.
5[6, 15]-[6, 15][2, 12, 20]save levellevels is now [[10], [6, 15]].
6[2, 12, 20]2[2][4]only a right child2 has no left child but has a right child 4. The left check fails and the right check passes.
7[2, 12, 20]12[2, 12][4]no children12 is a leaf, so next doesn't change.
8[2, 12, 20]20[2, 12, 20][4]no children20 is a leaf too.
9[2, 12, 20]-[2, 12, 20][4]save levelThe third level is saved. Only 4 waits for the next round.
10[4]4[4][]no children4 is a leaf, so next stays empty.
11[4]-[4][]save level, then stopqueue becomes [], so the while condition is false and the loop ends.

[[10], [6, 15], [2, 12, 20], [4]]. The loop ran 4 rounds, one per level, and stopped because the last level had no children to put in next. Each of the 7 nodes was read exactly once.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Level-order traversal (tree BFS)O(n)O(w)You need rows, an answer per level, or the shallowest match.
DFS with a depth parameterO(n)O(h)Call visit(node, depth) and push into levels[depth]. Same output with less memory on wide trees, but it fills all levels at once, so it can't stop early at the shallowest match.
One full DFS per depthO(n²)O(h)Never in practice. It's the slow starting point, shown here so the gap is clear.

Extra memory: O(w), where w is the widest level, because queue and next hold at most two neighboring levels. A chain needs O(1), and a perfect tree's bottom level is about n / 2, so O(n). The levels output adds O(n).

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Level-order traversal (tree BFS) and the other approaches, on a scale where each line up is 10 times more steps.
  • Level-order traversal (tree BFS), DFS with a depth parameter O(n)
  • One full DFS per depth O(n²)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Level-order traversal (tree BFS)101,0001 million
DFS with a depth parameter101,0001 million
One full DFS per depth1001 million1 trillion

Inputs that need care

5 tricky inputs
An empty tree: root = null
Line 3 returns [] before the queue is made, so null never enters queue and node.val is never read on null.
One node: root = [5]
One round: level = [5] and next = []. The answer is [[5]].
A chain leaning right: 1, then 2, then 3
Each round holds one node, so the answer is [[1], [2], [3]]. The if (node.left) check fails every time and only the right child is added.
A child node whose value is 0
if (node.left) tests the child node object, not its value, so a child holding 0 is still added. Writing if (node.left.val) would wrongly skip it, and would crash on a missing child.
A very wide tree, like an n-ary node with thousands of children
Memory grows with that width. If you only need the first few levels, stop the while loop once you reach the depth you need.

Variations and follow-ups

Twists interviewers add

Right side view

Keep only the last node of each level, the one you'd see looking at the tree from the right side. With this code it's level[level.length - 1] after each round.

Zigzag order

Reverse every other level before saving it, so rows alternate between left-to-right and right-to-left. Don't change the order children are added to next, or every later level gets scrambled.

One array with a level size

Many write it with one array and a head index. At the start of a round, save size = queue.length - head, then handle exactly size nodes. It does the same work with one list and keeps each step O(1), because nothing is shifted.

Stop at the shallowest match

Levels come out in order of depth, so the first node you meet that matches a check is the shallowest one. Return the round number there and stop. For "minimum depth", that's the round of the first leaf.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from the words "level", "row", "depth by depth", "right side view", "minimum depth", or an answer shaped like a list of lists.
  • Say the rule: "at the start of each round, queue is exactly one level". It explains why the two lists are separate and why the left child is added before the right one.
  • Test a tree with a gap, like [1, 2, 3, null, 4]. The gap must not appear as null in the output, and 4 must be in the third row.
  • A common follow-up is "find the minimum depth". BFS returns the round number of the first leaf it meets, which can be much faster than a DFS that first explores a deep left branch.

Where frontend code uses it

The same idea in real UI code
  • An org chart or sitemap view draws people or pages row by row, which is level-order on the tree.
  • When you need the closest element that matches a check (the nearest focusable child, for example), a level-by-level search of the DOM finds the shallowest match first, while a depth-first search could return a deep one in an early branch.
  • A tree view that is opened "to depth 2" only needs the first three levels, which is a level-order walk that stops early.

Related algorithms