Left View of Binary Tree — Solution in Python, Java & C++
Left View of Binary Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Left View of Binary Tree is an easy coding problem on depth-first search, breadth-first search and trees, asked in Amazon, Flipkart, Samsung and Paytm interviews.
- Difficulty: Easy
- Topics: Depth-First Search, Breadth-First Search, Trees
- Asked at: Amazon, Flipkart, Samsung, Paytm
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
The left view of a binary tree is the set of nodes you would see standing to the left of it: the first (leftmost) node of every level.
Given the root of a binary tree, return the values of its left view from the top level down. Return an empty list for an empty tree.
Example 1
Input: root = [1,2,3,4,5,6,7,null,8]
Output: [1,2,4,8]
Explanation: Looking from the left you see 1, then 2, then 4, and finally 8 on the deepest level.
Example 2
Input: root = [1,null,2,null,3]
Output: [1,2,3]
Explanation: Every level holds one node, so each is the first on its level even though they hang to the right.
Example 3
Input: root = []
Output: []
Explanation: An empty tree shows nothing.
Constraints
0 <= number of nodes <= 10^50 <= Node.val <= 10^5
Hints for Left View of Binary Tree
Hint 1
The answer has exactly one value per level.
Hint 2
A level-order traversal (BFS) meets each level's nodes from left to right — take the first one of every level.
Hint 3
Alternatively, a depth-first search that visits left before right reaches each depth first through its leftmost node: record a node when its depth equals the number of values collected so far.
How to solve Left View of Binary Tree
Process the tree one level at a time; the first node dequeued on each level is the one seen from the left.
Approach
- If the tree is empty, return an empty list.
- Put the root in a queue.
- While the queue is not empty: note
size, the number of nodes on the current level, and append the value of the node at the front. - Dequeue those
sizenodes, enqueuing each one's left child then right child. - Return the collected values.
Why it works
Children are enqueued left before right and level by level, so the queue always holds one complete level in left-to-right order when a new level starts, and its front is that level's leftmost node.
Complexity
- Time —
O(n) - Space —
O(w), w the largest number of nodes on one level
Pitfalls
- The leftmost node of a level need not be a left child — on a level reached only through right children it is a right child.
- Iterative traversal avoids the deep recursion a 10^5-node chain would cause.
Reference solution
Python
from collections import deque
from typing import List, Optional
def leftView(root: Optional[TreeNode]) -> List[int]:
out = []
queue = deque([root]) if root else deque()
while queue:
out.append(queue[0].val)
for _ in range(len(queue)):
node = queue.popleft()
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return outJava
public static int[] leftView(TreeNode root) {
List<Integer> out = new ArrayList<>();
Deque<TreeNode> queue = new ArrayDeque<>();
if (root != null) queue.add(root);
while (!queue.isEmpty()) {
out.add(queue.peek().val);
for (int i = queue.size(); i > 0; i--) {
TreeNode node = queue.poll();
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
}
int[] res = new int[out.size()];
for (int i = 0; i < res.length; i++) res[i] = out.get(i);
return res;
}C++
vector<int> leftView(TreeNode* root) {
vector<int> out;
queue<TreeNode*> q;
if (root) q.push(root);
while (!q.empty()) {
out.push_back(q.front()->val);
for (int i = (int) q.size(); i > 0; i--) {
TreeNode* node = q.front();
q.pop();
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
return out;
}JavaScript
var leftView = function(root) {
var out = [];
if (root === null) return out;
var queue = [root], head = 0;
while (head < queue.length) {
var end = queue.length;
out.push(queue[head].val);
while (head < end) {
var node = queue[head++];
if (node.left !== null) queue.push(node.left);
if (node.right !== null) queue.push(node.right);
}
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)