Right/Left view of Binary Tree
What you see from the sides
The left view of a binary tree is the set of nodes visible when looking at it from the left side — the first node at each level. The right view is the same from the right — the last node at each level. Two approaches: brute force (BFS + pick first/last) and optimal (DFS with level tracking).
Brute Force — the tree and the idea
The brute force approach uses BFS (level-order traversal) to collect all nodes level by level, then simply picks the first element of each level for the left view and the last element of each level for the right view. The tree used in the brute force code:
1queue q;
2q.push(root);
3
4while (!q.empty()) {
5 int size = q.size();
6 vector<int> level;
7 for (int i = 0; i < size; i++) {
8 Node* node = q.front(); q.pop();
9 level.push_back(node->data);
10 if (node->left) q.push(node->left);
11 if (node->right) q.push(node->right);
12 }
13 ans.push_back(level);
14}Expected: Left View = [1, 2, 4] · Right View = [1, 3, 5]
Brute Force — BFS produces the level-order table
The BFS queue processes nodes level by level. At each iteration of the outer while loop,
it captures the current queue size (= number of nodes at this level), then processes exactly that many nodes.
Children are enqueued for the next level. The result is a 2D vector — one sub-vector per level.
| Level | Nodes (left → right) | First (left view) | Last (right view) |
|---|---|---|---|
| 0 | 1 | 1 | 1 |
| 1 | 2 → 3 | 2 | 3 |
| 2 | 4 → 5 | 4 | 5 |
1// Iteration 1: size=1 → process node 1 → level=[1] → push 2,3
2// Iteration 2: size=2 → process 2,3 → level=[2,3] → push 4,5
3// Iteration 3: size=2 → process 4,5 → level=[4,5] → no children
4
5ans = { {1}, {2,3}, {4,5} } // 2D vector: one row per levelBrute Force — pick first and last of each level
Once the full level-order traversal is stored, extracting the views is trivial. The left view takes
level[0] from each row; the right view takes level.back(). Simple — but it required
storing the entire 2D traversal in memory, even though only one node per level is needed.
{1,2} → first of [2,3]
{1,2,4} → first of [4,5]
{1,3} → last of [2,3]
{1,3,5} → last of [4,5]
1// Left View: pick first element of each level
2for (auto& level : levels)
3 left.push_back(level[0]); // first = leftmost
4
5// Right View: pick last element of each level
6for (auto& level : levels)
7 right.push_back(level.back()); // last = rightmostOptimal — the tree and the idea
The optimal approach uses DFS (pre-order traversal) with a clever trick: track the current depth
(level) as you recurse. When you encounter a level for the first time
(res.size() == level), the current node is the first one visited at that depth — add it to the result.
For the left view, recurse left first; for the right view, recurse right first.
No queue, no 2D vector — just a single result vector and the recursion stack.
1void leftDFS(TreeNode* node,
2 int level, vector<int>& res) {
3 if (!node) return;
4
5 // First time reaching this level?
6 if (res.size() == level)
7 res.push_back(node->val);
8
9 // Left first → leftmost node
10 leftDFS(node->left, level+1, res);
11 leftDFS(node->right, level+1, res);
12}
For rightDFS, swap the recursion order:
right first → rightmost node
Expected: Left View = [1, 2, 4, 5, 6] · Right View = [1, 3, 4, 5, 6]
Optimal — Left DFS trace (left child first)
The DFS visits nodes in pre-order, always going left first. The condition
res.size() == level is true only the first time a depth is reached — and because
left is explored first, that first node is the leftmost one at that level. Once a level is "claimed",
all other nodes at the same depth are skipped.
Optimal — Right DFS trace (right child first)
Same logic, but the recursion order is swapped: right child first, then left. This means the first node encountered at each depth is the rightmost one. Node 3 is visited at level 1 before node 2, so 3 claims that level. But node 2's right chain (4, 5, 6) descends through levels 2-4 that node 3 couldn't reach (it has no children), so 4, 5, 6 are all claimed on the way back.
Brute Force vs Optimal — side by side
Both approaches produce the same result, but the optimal one is more memory-efficient. The brute force stores the entire level-order traversal (a 2D vector with all N nodes) just to pick one node per level. The optimal approach uses only a single result vector and the recursion stack — no extra storage for intermediate data.
| Aspect | Brute Force (BFS) | Optimal (DFS) |
|---|---|---|
| Technique | BFS level-order, then pick level[0] / level.back() |
DFS pre-order with res.size() == level check |
| Data structures | queue + 2D vector (all levels stored) |
Single result vector + recursion stack |
| Traversal order | Level by level (breadth-first) | Depth-first (left-first for left view, right-first for right view) |
| Key insight | First/last element of each level = left/right view | First node visited at a new depth = view node (order determines which view) |
| Time complexity | O(N) — every node visited once | O(N) — every node visited once |
| Space complexity | O(N) — queue + 2D vector stores all nodes | O(H) — only recursion stack (H = tree height) |
| Two passes? | Yes — BFS then iterate to extract (but reuses same levels vector) |
No — single DFS pass builds the result directly |
| Best for | When you also need the full level-order traversal for other purposes | When you only need the view — minimal memory, clean code |
// Left View: recurse LEFT first → leftmost node claims each level
leftDFS(node->left, level + 1, res); // ← left first
leftDFS(node->right, level + 1, res);
// Right View: recurse RIGHT first → rightmost node claims each level
rightDFS(node->right, level + 1, res); // ← right first
rightDFS(node->left, level + 1, res);Both approaches find the side views
The brute force approach is intuitive — build the level-order table, pick the edges. The optimal approach is
elegant — a single DFS pass where the recursion order determines which side you see. The key insight is that
res.size() == level acts as a "first visit" detector: it's true exactly once per depth, and the
node that triggers it is the view node for that level.
levels vector.