Medium Queue by Level Trees
In plain English: Visit every node in a binary tree level by level, from top to bottom.
A queue processes nodes in discovery order — processing one full level before the next gives breadth-first traversal.
Prompt
Return the level-order traversal of a binary tree as list of lists.
Try to write it from scratch before scrolling down.
Solution
from collections import deque
def level_order(root):
if not root:
return []
result = []
q = deque([root])
while q:
level = []
# process entire level before next
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)
result.append(level)
return result
# Test: BST [4,2,6,1,3] => [[4], [2,6], [1,3]]