Binary Tree Level Order Traversal

Medium#102tree nodes

You get the root of a binary tree, possibly none. Return its values level by level: a list per level, from the top down and left to right within a level. Our example is the tree [7, 4, 9, 1, none, 6, 12, none, 3, 8] in level order — the answer is [[7], [4, 9], [1, 6, 12], [3, 8]].

102 Binary Tree Level Order TraversalWalkthrough · 1×

Example: list the values of a lopsided four-level tree level by level.

749161238queuefront on the left—
not reachedin the queue, this levelin the queue, next levelcurrentlisted

The root is 7, not none

01/62
restart · back · play · step
Speed
1function levelOrder(root):
2 if root is none:
3 return []
4 result = []
5 queue = [root]
6 while queue is not empty:
7 size = queue.size
8 level = []
9 for i from 1 to size:
10 node = queue.popFront()
11 level.add(node.val)
12 for each child of node that is not none:
13 queue.pushBack(child)
14 result.add(level)
15 return result
state
result
–
queue
–
size
–
level
–
i
–
node
–
child
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. The queue gives nodes out in the order they came in, so a whole level leaves it before any node of the level below.
  2. When a level starts, the queue holds exactly that level. size is read then, so the loop stops at the level’s end, even though children of the next level are already queued behind it.
  3. Children go in left first, so each level comes out left to right, whichever parent a node hangs from.

Complexity

Time O(n): each node enters and leaves the queue once. Memory O(n): the answer holds every value, and the queue up to about two levels.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.