Return the leftmost value on each level of the tree, top to bottom (the "left view" of the tree).
leftyNodes(root)
Input format: level-order with x for missing children. Output the values
space-separated.
3 11 4 4 x x 2 // → 3 11 4
1 2 3 x 4 // → 1 2 4
(empty) // → (empty)
"The leftmost value on each level" is a question about the tree's structure level by level, not about any single root-to-leaf path. Depth-first search dives deep into one branch before backing out, making "what's the first node reached at depth 3?" awkward — you'd need to track depth separately from the traversal. It's fighting the grain.
BFS processes the tree in exactly the order this cares about: every node at depth 0, then depth 1, then depth 2, using a queue. Since BFS naturally groups work into complete levels, "the first node processed in this level's group" is directly the leftmost node — no separate depth bookkeeping.
The trick — "first dequeued this round is leftmost" — depends entirely on left-to-right enqueue order at every level. Enqueue right-before-left even once, and the leftmost node of the next level could land anywhere in the queue.
Every node is enqueued and dequeued once at constant cost — O(n) time. The queue can hold as many nodes as the widest level, up to O(n) in the worst case (a wide, shallow tree).
def lefty_nodes(root):
if root is None:
return []
result = []
queue = deque([root])
while queue:
size = len(queue)
for i in range(size):
node = queue.popleft()
if i == 0:
result.append(node.val)
if node.left is not None:
queue.append(node.left)
if node.right is not None:
queue.append(node.right)
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.