Left View of Binary Tree

The Left View of a Binary Tree is a classic tree-traversal question. Picture yourself standing to the left of the tree, looking right: at each level you see exactly one node — the leftmost one. Return those nodes, top to bottom.

      1
    /   \
   2     3
  / \     \
 4   5     7

The slow way first

You could collect every level into its own list (a full level-order traversal), then take element 0 of each list. That works and is O(n) time — but it stores whole levels just to keep their first element. We can be tidier: while we walk a level, we already know which node is first, so we can grab it on the fly and never build the throwaway lists.

The question to ask: as I process a level, how do I know which node is the leftmost? If the queue always holds one full level in left-to-right order, the leftmost node is simply the first one I dequeue for that level.

The idea: BFS, grab the first of each level

Do a breadth-first traversal (BFS) with a queue. The trick is to process the queue one full level at a time: record the queue's size, then dequeue exactly that many nodes. The first node dequeued in each batch (i == 0) is the leftmost node of that level — add it to the answer. As you dequeue each node, enqueue its children left-to-right so the next level stays in order.

The key insight: because children are enqueued left-to-right, the queue for any level is always in left-to-right order. So the front of that level is the node the left view sees.

Walk through it

Step through the animation. The queue starts with the root 1. For each level we mark the first node success (it joins the left view) and the rest dim (skipped). Level 0 gives 1, level 1 gives 2 (3 is skipped), level 2 gives 4 (5 and 7 skipped). When the queue empties we return [1, 2, 4].

Pseudocode

if the tree is empty: return an empty list
make a queue holding just the root
view = empty list
while the queue is not empty:
    size = how many nodes are in the queue   # one whole level
    repeat size times, with counter i from 0:
        node = dequeue from the front
        if i == 0:                            # leftmost node of this level
            append node value to view
        enqueue node.left  if it exists
        enqueue node.right if it exists
return view

The Python solution

from collections import deque
 
def left_view(root):
    if not root:
        return []
    view, queue = [], deque([root])
    while queue:
        size = len(queue)
        for i in range(size):
            node = queue.popleft()
            if i == 0:
                view.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    return view

• deque gives an O(1) popleft — a plain list's pop(0) is O(n), so prefer deque for a queue.
• An empty tree has no left view, so we return [] immediately.
• size = len(queue) freezes how many nodes belong to the current level before we start adding the next level's children.
• The loop counter i tracks position within the level. i == 0 means leftmost, so that node's value is appended to view.
• We always enqueue node.left before node.right, which keeps every level in left-to-right order.

Complexity

We touch each of the n nodes a single time, so it is O(n) time. The space is O(n) for the queue — at its widest a level can hold up to about half the nodes, which is still O(n).

When this pattern shows up

Practice