For each level of the tree (top to bottom), return the number of leaf nodes on that level.
leafLayers(root)
Input format: level-order with x for missing children. Output one count per level,
space-separated.
3 9 20 x x 15 7 // → 0 1 2 (level0: no leaves; level1: 9; level2: 15,7)
1 // → 1
(empty) // → (empty)
A per-level count is a strong signal to process the tree level by level, not root-to-leaf along one branch — pointing directly at BFS with a queue rather than DFS.
With plain BFS, nodes from different levels mix in the queue as you go, so the trick is processing in level-sized batches. At the start of each round, note the current queue size — that's exactly the current level's size, since every queued node was enqueued by the previous level. Dequeue exactly that many before moving on; children enqueued along the way only get picked up next round.
A leaf has no children — both left and right pointers empty. Dequeuing each node in the batch, check for children. None means count it as a leaf for this level. Some means enqueue them for the next level, but this node itself doesn't count.
After a level's batch, append its leaf count to the results before the next batch. Repeat until the queue is empty — every node enqueued once, dequeued once.
You could track depth during DFS and increment result[depth] at each leaf — a valid, also O(n) alternative. But BFS fits more naturally: the problem is fundamentally about grouping by level, and BFS's queue gives you those groupings for free, no depth argument needed.
Every node is enqueued and dequeued once — O(n) total either way. The BFS queue needs O(n) space worst case, for a wide, shallow tree.
def leaf_layers(root):
if root is None:
return []
result = []
queue = [root]
while len(queue) > 0:
size = len(queue)
leaves = 0
for _ in range(size):
node = queue.pop(0)
if node.left is None and node.right is None:
leaves += 1
if node.left is not None:
queue.append(node.left)
if node.right is not None:
queue.append(node.right)
result.append(leaves)
return result
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.