JuniorJunior (1–3 yrs)CodingPythonAmazonMicrosoftMeta
Binary Tree Level Order Traversal
Return the level-order traversal of a binary tree's values (left to right, level by level).
Answers use simple, clear English.
Audio N/ATime: O(n)Space: O(w)
Quick interview answer
BFS with a queue. Process the queue length at the start of each level to batch that level's nodes into one list.
Detailed answer
BFS with a queue. Process the queue length at the start of each level to batch that level's nodes into one list. DFS with depth index also works but BFS is the natural fit.
Full explanation
DFS with depth index also works but BFS is the natural fit.
Real example & use case
Rendering an org chart one management layer at a time for progressive disclosure.
Pros & cons
Pros: clear levels. Cons: O(w) queue memory for wide trees.
Code example
from collections import deque
def level_order(root) -> list[list[int]]:
if not root:
return []
q, res = deque([root]), []
while q:
level = []
for _ in range(len(q)):
node = q.popleft()
level.append(node.val)
if node.left: q.append(node.left)
if node.right: q.append(node.right)
res.append(level)
return resPractice code · python (view only · no execution)
from collections import deque
def level_order(root) -> list[list[int]]:
if not root:
return []
q, res = deque([root]), []
while q:
level = []
for _ in range(len(q)):
node = q.popleft()
level.append(node.val)
if node.left: q.append(node.left)
if node.right: q.append(node.right)
res.append(level)
return res#bfs#tree