Binary Tree Left Side View

Given a binary tree, return all the values you'd be able to see if you were standing on the left side of it with values ordered from top to bottom.

Example(s)

Example 1:

Tree:
    4
   / \
  2   7
Output: [4,2]

Example 2:

Tree:
        7
       / \
      4   9
     / \ / \
    1  4 8  9
             \
              9
Output: [7,4,1,9]

Solution

JavaScript Solution

JavaScript Left Side View Solution

function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val);
this.left = (left===undefined ? null : left);
this.right = (right===undefined ? null : right);
}

/**
* Return the left side view of a binary tree
* @param {TreeNode} root - Root of the binary tree
* @return {number[]} - Array of values visible from the left side
*/
function leftSideView(root) {
if (!root) return [];

const result = [];
const queue = [root];

while (queue.length) {
  const levelSize = queue.length;
  
  for (let i = 0; i < levelSize; i++) {
    const node = queue.shift();
    if (i === 0) result.push(node.val); // Take the first node of each level
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
}

return result;
}

// Test case 1: [4,2,7]
const tree1 = new TreeNode(4);
tree1.left = new TreeNode(2);
tree1.right = new TreeNode(7);

// Test case 2: [7,4,9,1,4,8,9,null,null,null,9]
const tree2 = new TreeNode(7);
tree2.left = new TreeNode(4);
tree2.right = new TreeNode(9);
tree2.left.left = new TreeNode(1);
tree2.left.right = new TreeNode(4);
tree2.right.left = new TreeNode(8);
tree2.right.right = new TreeNode(9);
tree2.right.right.right = new TreeNode(9);

// Test cases
console.log(leftSideView(tree1)); // [4,2]
console.log(leftSideView(tree2)); // [7,4,1,9]
console.log(leftSideView(null)); // []

Output:

Click "Run Code" to execute the code and see the results.

Python Solution

Python Left Side View Solution

from typing import Optional, List
from collections import deque

# Definition for a binary tree node.
class TreeNode:
  def __init__(self, val=0, left=None, right=None):
      self.val = val
      self.left = left
      self.right = right

def left_side_view(root: Optional[TreeNode]) -> List[int]:
  """
  Return the left side view of a binary tree
  
  Args:
      root: Root of the binary tree
      
  Returns:
      List[int]: Array of values visible from the left side
  """
  if not root:
      return []
  
  result = []
  queue = deque([root])
  
  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

# Test case 1: [4,2,7]
tree1 = TreeNode(4)
tree1.left = TreeNode(2)
tree1.right = TreeNode(7)

# Test case 2: [7,4,9,1,4,8,9,null,null,null,9]
tree2 = TreeNode(7)
tree2.left = TreeNode(4)
tree2.right = TreeNode(9)
tree2.left.left = TreeNode(1)
tree2.left.right = TreeNode(4)
tree2.right.left = TreeNode(8)
tree2.right.right = TreeNode(9)
tree2.right.right.right = TreeNode(9)

# Test cases
print(left_side_view(tree1))  # [4,2]
print(left_side_view(tree2))  # [7,4,1,9]
print(left_side_view(None))  # []

Loading Python runtime...

Output:

Click "Run Code" to execute the code and see the results.

Complexity

• Time Complexity: O(n) - Where n is the number of nodes in the tree
• Space Complexity: O(w) - Where w is the maximum width of the tree

Approach

The solution uses a breadth-first search (BFS) approach:

1. Level-by-level traversal using a queue
2. Capture first node of each level (leftmost visible node)
3. Process all nodes at each level to maintain proper order
4. Return array of leftmost values from each level

Key Insights

• Breadth-first search ensures level-by-level traversal to capture the leftmost node
• Queue data structure efficiently processes nodes in order
• First node per level represents the left side view
• Edge cases include empty tree, single-node tree, and skewed trees
• O(n) time is optimal as all nodes may need to be visited to construct the view