Left View of Binary Tree

Easy
1890.

Left View of Binary Tree

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.

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^5
  • 0 <= Node.val <= 10^5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var leftView = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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^5
  • 0 <= Node.val <= 10^5

Hints for Left View of Binary Tree

  1. Hint 1

    The answer has exactly one value per level.

  2. Hint 2

    A level-order traversal (BFS) meets each level's nodes from left to right — take the first one of every level.

  3. 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

  1. If the tree is empty, return an empty list.
  2. Put the root in a queue.
  3. 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.
  4. Dequeue those size nodes, enqueuing each one's left child then right child.
  5. 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 out

Java

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)