Left View of a Binary Tree - Algorithm, Visualization, Examples

Contents

ProblemExamplesVisualizationSolutionAlgorithmCode

Problem Statement❯

Given a binary tree, return the left view of the tree. The left view of a binary tree contains the nodes that are visible when the tree is viewed from the left side. You must consider the leftmost node at each level of the tree and collect them in a top-down manner.

Examples❯

Input Tree Left View Output Description
[1, 2, 3, 4, 5, null, 6]
[1, 2, 4] Standard binary tree with left and right children; leftmost node at each level forms the left view
[1]
[1] Single node tree; the root is the only node and hence the left view
[] [] Empty tree; no nodes result in an empty left view
[1, 2, null, 3, null, null, null, 4]
[1, 2, 3, 4] Left-skewed tree; each level has only one leftmost node
[1, null, 2, null, null, null, 3]
[1, 2, 3] Right-skewed tree; the first node at each level still defines the left view
[10, 5, 15, 3, 7, null, 18]
[10, 5, 3] Binary search tree; leftmost visible node from each level contributes to the left view

Visualization Player

Solution❯

Case 1: Standard Binary Tree

In a typical binary tree with nodes having both left and right children, we use level order traversal (Breadth First Search) and pick the first node we encounter at each level. Since we go level by level from top to bottom, and at each level, from left to right, the first node is always the leftmost node of that level. These nodes, when collected, give us the left view of the tree. For example, in the tree [1, 2, 3, 4, 5, 6], the left view is [1, 2, 4].

Case 2: Left-Skewed Tree

If the binary tree is skewed to the left, meaning every node has only a left child, then all the nodes are visible from the left side. So, the left view will include all the nodes from top to bottom. For instance, for the tree [10, 20, 30], the output is [10, 20, 30].

Case 3: Right-Skewed Tree

Although this may seem unintuitive, even in a right-skewed tree where all nodes are on the right, the first node we visit at each level is still visible from the left. That’s because there is only one node per level, and no left child to block it. Therefore, the left view will also include all nodes, like [7, 8, 9] for the example given.

Case 4: Empty Tree

If the tree is empty, there are no nodes to view. So the left view is simply an empty list: [].

Case 5: Uneven Tree with Missing Children

Sometimes a binary tree may have some levels where the left child is missing but a right child is present. In such cases, during level order traversal, we must ensure that the first node encountered in the level is added to the left view, regardless of whether it's a left or right child. This ensures the left view remains accurate even in uneven trees.

Algorithm Steps❯

  1. If the binary tree is empty, return an empty list.
  2. Initialize a queue and add the root node.
  3. While the queue is not empty, determine the number of nodes at the current level.
  4. For each node at the current level, dequeue the node. If it is the first node in this level, record its value.
  5. Enqueue the left and right children of the node, if they exist.
  6. Repeat until all levels are processed. The recorded values form the left view of the tree.

Code

Python
Java
JavaScript
C
C++
C#
Kotlin
Swift
Go
Php
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

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

if __name__ == '__main__':
    # Construct binary tree:
    #         1
    #       /   \
    #      2     3
    #     / \     \
    #    4   5     6
    root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, None, TreeNode(6)))
    print(leftView(root))