Return the values of the tree grouped by level: index 0 is the root's level, index 1 the next, and so on, each in left-to-right order.
treeLevels(root)
Input format: level-order with x for missing children. Output each level's
values space-separated, with levels separated by | (e.g. 3 | 9 20 | 15 7).
3 9 20 x x 15 7 // → [[3] [9 20] [15 7]] → "3 | 9 20 | 15 7"
1 2 3 // → [[1] [2 3]] → "1 | 2 3"
(empty) // → [] → ""
Plain breadth-first traversal gives you every node in level order as one flat sequence, but it doesn't mark where one level ends and the next begins — that boundary is lost once everything's in one list. This problem asks you to preserve it.
In a queue-based BFS, at the instant you're about to start a new level, the queue contains exactly that level's nodes and nothing else — no next-level nodes have been added yet, since those only get enqueued as you process the current level. So checking the queue's length at that exact moment, before dequeuing anything for this round, tells you precisely how many nodes belong to the current level.
This works because children enqueued during round N always belong to level N+1, and capturing the size before any of those get dequeued draws a hard line between this round's nodes and next round's.
This is the same queue-based level-order traversal as plain BFS — the only addition is snapshotting the size before each round, turning a flat sequence into level-grouped output with no extra data structure.
Every node is still enqueued and dequeued once, so total work is proportional to the number of nodes, with the queue bounded by the tree's widest level.
def tree_levels(root):
if root is None:
return []
levels = []
queue = [root]
i = 0
while i < len(queue):
size = len(queue) - i
level = []
for _ in range(size):
node = queue[i]
i += 1
level.append(node.val)
if node.left is not None:
queue.append(node.left)
if node.right is not None:
queue.append(node.right)
levels.append(level)
return levels
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.