Left View of Binary Tree

Given the root of a binary tree, imagine standing on its left side. Return the values of the nodes you can see, ordered from top to bottom — that is, the leftmost node at each level.

The tree is given in level-order (breadth-first), using null for missing children.

Hints

· Stuck? Reveal one nudge at a time.

The visible node at each level is the leftmost one.

In level-order BFS that's simply the first node dequeued on each level.

A DFS that goes left before right records the first node it reaches at each new depth.

Common doubts

No — if a level's leftmost node lacks a left child, the visible node can descend from a right child; it's the leftmost node, not the left child.

Going left before right, the first node reached at any depth is the leftmost at that depth, so you record on first arrival.

The mirror: the last node of each level in BFS, or a right-first DFS.

Interview follow-ups

· What an interviewer asks next.

Take the last node of each level in BFS, or recurse right-before-left and record the first node at each depth.

Group nodes by horizontal distance instead of level, keeping the first (top) or last (bottom) node per column.

Fun facts

The left-side and right-side views are exact mirrors: swap 'first' and 'last' of each level.
Left-first DFS computes the view with O(height) space instead of O(width).

Asked at

AmazonMicrosoftPaytm

Frequently Sometimes Occasionally

Example 1

Input: root = [1, 2, 3, 4, 5, null, null, null, 6]
Output: [1, 2, 4, 6]
From the left you see the leftmost node at each of the four levels.

Example 2

Input: root = [1, null, 3]
Output: [1, 3]
The 3 is the leftmost (only) node on level 1, even though it's a right child.

Example 3

Input: root = []
Output: []
An empty tree shows nothing.

Constraints

- The number of nodes is in the range [0, 100] - 1 <= Node.val <= 10^5

Standing on the left, the node you see at each level is the leftmost one. So this is level-order traversal where you keep only the first node of each level. Equivalently, a depth-first walk that visits the left child first and records the first node it reaches at each new depth.

Prerequisites

Before you start

· Concepts used directly in the solution.

Level-order traversal. BFS by level — the first node of each level is the left-side view.

Depth-tracking DFS. Left-first DFS records the first node seen at each depth.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Definition

“Leftmost node, or only left children?”

The leftmost node at each level, which may be a right child if the left side is missing.

“Empty tree?”

Return an empty list.

The ideal opening — say it like this

The left-side view is the first node of each level, so I run level-order BFS and keep the first node of every level.

Or I DFS left-child-first and record the first node I reach at each new depth.

Understand the problem

Worked example — tree [1, 2, 3, 4, 5, null, null, null, 6]

        1
       / \
      2   3
     / \
    4   5
         \
          6
level 0: leftmost 1
level 1: leftmost 2
level 2: leftmost 4
level 3: leftmost 6
result: [1, 2, 4, 6]

Key observations

1Aha

Left-side view = first node per level

It's level-order with everything but each level's first node discarded.

2Aha

A right child can be visible

If a level's leftmost node has no left child, its leftmost may descend from a right child.

3Aha

Left-first DFS is equivalent

Recursing left before right reaches each depth's leftmost node first; record on first arrival at a depth.

Brute force vs optimal

	Left-first DFS	BFS first-of-level
Idea	Record first node reached at each new depth	Keep the first node dequeued per level
Time	O(n)	O(n)
Space	O(height)	O(n)

Both are O(n); BFS reads directly as 'first of each level'. Full code is in the Approaches selector below.

Summary

Key takeaway

The left-side view is the leftmost (first) node at each level. Take it from level-order BFS, or from a left-first DFS that records the first node at each new depth. O(n) time.

bfs level by level:
    append the first node of each level to the result