Left Side View of Binary Tree in DSA Java - Execution Trace

Concept Flow - Left Side View of Binary Tree

Start at root node

↓

Traverse level by level

↓

At each level, visit nodes left to right

↓

Record first node encountered at each level

↓

Add recorded nodes to left side view list

↓

Repeat until all levels processed

↓

Return left side view list

We visit the tree level by level from left to right and record the first node at each level to get the left side view.

Execution Sample

DSA Java

import java.util.*;

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

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 size = queue.size();
    for (int i = 0; i < size; 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;
}

This code performs a level order traversal to collect the leftmost node at each level of the binary tree.

Execution Table

Step	Operation	Nodes in Queue	Visited Node	Left Side View List	Visual Tree State
1	Start with root	[1]	1	[1]	1 / \ 2 3 / \ 4 5
2	Visit level 2 nodes	[2,3]	2	[1,2]	1 / \ 2 3 / \ 4 5
3	Visit level 3 nodes	[3,4]	3	[1,2]	1 / \ 2 3 / \ 4 5
4	Visit level 4 nodes	[4,5]	4	[1,2,4]	1 / \ 2 3 / \ 4 5
5	Visit level 5 nodes	[5]	5	[1,2,4]	1 / \ 2 3 / \ 4 5
6	Queue empty, end	[]	-	[1,2,4]	1 / \ 2 3 / \ 4 5

💡 Queue is empty, all nodes visited, left side view collected

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	Final
Queue	[]	[1]	[2,3]	[3,4]	[4,5]	[5]	[]
Visited Node	-	1	2	3	4	5	-
Left Side View List	[]	[1]	[1,2]	[1,2]	[1,2,4]	[1,2,4]	[1,2,4]

Key Moments - 3 Insights

Why do we add only the first node at each level to the left side view?

Because the first node visited at each level is the leftmost node visible from the left side. This is shown in execution_table rows 1, 2, and 4 where the first visited nodes 1, 2, and 4 are added.

Why do we use a queue to traverse the tree?

A queue helps us visit nodes level by level (breadth-first). This ensures we see nodes from left to right at each level, as shown in the 'Nodes in Queue' column in execution_table.

What happens if the tree is empty?

If the root is null, the queue starts empty and the left side view list remains empty. The traversal ends immediately, returning an empty list.

Visual Quiz - 3 Questions

Look at the execution_table at Step 3, what is the left side view list?

A [1, 2, 4]

B [1, 2]

C [1, 3]

D [2, 4]

💡 Hint

Check the 'Left Side View List' column at Step 3 in the execution_table.

At which step does the queue become empty?

A Step 6

B Step 4

C Step 5

D Step 3

💡 Hint

Look at the 'Nodes in Queue' column to find when it becomes [].

If the node 2 had no left child, how would the left side view list change after Step 2?

A [1]

B [1, 3]

C [1, 2]

D [1, 4]

💡 Hint

Consider which node would be first at level 2 if node 2 has no left child, check execution_table logic.

Concept Snapshot

Left Side View of Binary Tree:
- Traverse tree level by level (BFS)
- At each level, record first node visited (leftmost)
- Use a queue to track nodes per level
- Return list of these first nodes as left side view
- Handles empty tree by returning empty list

Full Transcript

To find the left side view of a binary tree, we start at the root and visit nodes level by level from left to right. We use a queue to keep track of nodes at each level. At each level, we record the first node we visit because it is the leftmost visible node from that side. We continue until all levels are processed. If the tree is empty, we return an empty list. This method ensures we capture the left side view correctly.

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