Left Side View of Binary Tree in DSA Java

Mental Model

We want to see the nodes visible when looking at the tree from the left side, which means the first node at each level.

Analogy: Imagine standing on the left side of a tall building with many floors and windows; you only see the first window on each floor from your side.

      1
     / \
    2   3
   / \   \
  4   5   6

Left side view: 1 -> 2 -> 4 -> null

Dry Run Walkthrough

Input: Binary tree: 1 / \ 2 3 / \ \ 4 5 6

Goal: Print the leftmost node at each level: 1, 2, 4

Step 1: Start at root node 1, add it to queue

Queue: [1]

Why: We begin level order traversal from the root

Step 2: Process level 1: dequeue 1, record 1 as leftmost

Left side view: 1
Queue after enqueue children: [2, 3]

Why: First node at level 1 is 1, add its children for next level

Step 3: Process level 2: dequeue 2, record 2 as leftmost, enqueue children 4 and 5

Left side view: 1 -> 2
Queue: [3, 4, 5]

Why: First node at level 2 is 2, add its children for next level

Step 4: Continue level 2: dequeue 3, enqueue child 6

Left side view: 1 -> 2
Queue: [4, 5, 6]

Why: 3 is not leftmost at this level, but we add its child for next level

Step 5: Process level 3: dequeue 4, record 4 as leftmost

Left side view: 1 -> 2 -> 4
Queue: [5, 6]

Why: First node at level 3 is 4, add its children (none)

Step 6: Continue level 3: dequeue 5, no children

Left side view: 1 -> 2 -> 4
Queue: [6]

Why: 5 is not leftmost, no children to add

Step 7: Continue level 3: dequeue 6, no children

Left side view: 1 -> 2 -> 4
Queue: []

Why: 6 is not leftmost, no children to add

Result:

Left side view: 1 -> 2 -> 4 -> null

Annotated Code

DSA Java

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class LeftSideView {
    public static List<Integer> leftSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                if (i == 0) result.add(node.val); // first node at this level
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }
        return result;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.right = new TreeNode(6);

        List<Integer> leftView = leftSideView(root);
        for (int val : leftView) {
            System.out.print(val + " -> ");
        }
        System.out.print("null\n");
    }
}

queue.offer(root);

start level order traversal from root

int levelSize = queue.size();

determine number of nodes at current level

for (int i = 0; i < levelSize; i++) {

iterate over all nodes at this level

TreeNode node = queue.poll();

remove node from queue to process

if (i == 0) result.add(node.val);

record first node at this level as left side view

if (node.left != null) queue.offer(node.left);

add left child for next level

if (node.right != null) queue.offer(node.right);

add right child for next level

Output

1 -> 2 -> 4 -> null

Complexity Analysis

Time: O(n) because we visit every node once during level order traversal

Space: O(w) where w is the maximum width of the tree due to the queue storing nodes at each level

vs Alternative: Compared to recursive DFS, this BFS approach naturally processes nodes level by level, making it easier to pick the first node at each level without extra depth tracking.

Edge Cases

Empty tree (root is null)

Returns empty list, no nodes to view

DSA Java

if (root == null) return result;

Tree with only one node

Returns list with single node value

DSA Java

queue.offer(root);

Tree where some levels have only right children

Still correctly picks first node at each level (which may be right child)

DSA Java

if (i == 0) result.add(node.val);

When to Use This Pattern

When asked to find the visible nodes from one side of a binary tree, use level order traversal and pick the first node at each level to get the left side view.

Common Mistakes

Mistake: Adding all nodes at a level to the result instead of only the first one
Fix: Add node value to result only when processing the first node at that level (i == 0)

Mistake: Using preorder traversal which does not guarantee level order
Fix: Use BFS with a queue to process nodes level by level

Summary

Prints the first node visible at each level when looking at the tree from the left side.

Use when you need to see the leftmost nodes of each level in a binary tree.

The key insight is to do a level order traversal and pick the first node at each level.

Practice

1. What does the "Left Side View" of a binary tree represent?

easy

A. Nodes visible when the tree is viewed from the left side

B. Nodes visible when the tree is viewed from the right side

C. All leaf nodes of the tree

D. Nodes at the deepest level of the tree

Solution

1. Step 1: Understand the view perspective

   The left side view means looking at the tree from the left side, so only nodes visible from that side are included.

2. Step 2: Identify what nodes are visible

   Nodes that are the first in each level from the left are visible, so the leftmost nodes at each depth form the left side view.

3. Final Answer:

   Nodes visible when the tree is viewed from the left side -> Option A

4. Quick Check:

   Left side view = nodes visible from left side [OK]

Hint: Left side view shows first node at each level from left [OK]

Common Mistakes:

• Confusing left side view with right side view
• Including all leaf nodes instead of leftmost nodes
• Thinking it shows deepest nodes only

2. Which Java data structure is best suited to help find the left side view of a binary tree level by level?

easy

A. Queue

B. Stack

C. HashMap

D. ArrayList

Solution

1. Step 1: Identify traversal method for levels

   Level order traversal visits nodes level by level, which is needed to find leftmost nodes at each level.

2. Step 2: Choose data structure for level order

   Queue is used for breadth-first search (level order traversal) because it processes nodes in FIFO order.

3. Final Answer:

   Queue -> Option A

4. Quick Check:

   Level order traversal uses queue [OK]

Hint: Use queue for level order traversal to get left side view [OK]

Common Mistakes:

• Using stack which is for depth-first traversal
• Using HashMap which stores key-value pairs, not order
• Using ArrayList without order control

3. What is the output of the left side view for this binary tree?

    1
   / \
  2   3
 /     \
4       5

medium

A. [1, 4, 5]

B. [1, 3, 5]

C. [1, 2, 5]

D. [1, 2, 4]

Solution

1. Step 1: Identify leftmost nodes at each level

   Level 0: Node 1 is leftmost.
   Level 1: Node 2 is leftmost.
   Level 2: Node 4 is leftmost.

2. Step 2: Collect nodes in order

   Left side view nodes are [1, 2, 4].

3. Final Answer:

   [1, 2, 4] -> Option D

4. Quick Check:

   Left side nodes = [1, 2, 4] [OK]

Hint: Pick first node at each level from left [OK]

Common Mistakes:

• Choosing right child nodes instead of left
• Including nodes not visible from left
• Mixing order of nodes

4. Given this Java code snippet for left side view, what is the error?

void leftSideView(Node root) {
  Queue<Node> q = new LinkedList<>();
  q.add(root);
  while (!q.isEmpty()) {
    int size = q.size();
    for (int i = 0; i < size; i++) {
      Node curr = q.poll();
      if (i == 0) System.out.print(curr.data + " ");
      if (curr.left != null) q.add(curr.left);
      if (curr.right != null) q.add(curr.right);
    }
  }
}

medium

A. Printing all nodes instead of only left side nodes

B. Using poll() instead of peek() to get current node

C. No check if root is null before adding to queue

D. Incorrect loop condition in for loop

Solution

1. Step 1: Check root handling

   The code adds root to queue without checking if root is null, which can cause NullPointerException.

2. Step 2: Verify other parts

   Using poll() is correct to remove and get node.
   Printing only when i==0 prints leftmost node.
   Loop condition is correct for level size.

3. Final Answer:

   No check if root is null before adding to queue -> Option C

4. Quick Check:

   Null root check missing causes error [OK]

Hint: Always check if root is null before processing [OK]

Common Mistakes:

• Ignoring null root causing runtime error
• Confusing poll() with peek() usage
• Printing all nodes instead of leftmost only

5. How would you modify the left side view algorithm to return the left side view nodes in reverse order (bottom to top)?

hard

A. Traverse the tree in reverse level order using a queue

B. Use a stack to store leftmost nodes during level order, then pop all

C. Use recursion to collect nodes and reverse the list at the end

D. Print nodes during traversal without storing them

Solution

1. Step 1: Understand normal left side view collection

   Normally, leftmost nodes are collected in order from top to bottom during level order traversal.

2. Step 2: Modify to reverse order

   Store leftmost nodes in a stack during traversal, then pop all to get bottom-to-top order.

3. Final Answer:

   Use a stack to store leftmost nodes during level order, then pop all -> Option B

4. Quick Check:

   Stack reverses order of collected nodes [OK]

Hint: Use stack to reverse order of collected left side nodes [OK]

Common Mistakes:

• Trying to reverse queue order directly
• Not storing nodes before printing
• Using recursion without reversing result