Left Side View of Binary Tree in DSA C# - Execution Trace

Concept Flow - Left Side View of Binary Tree

Start at root node

↓

Initialize queue with root

↓

While queue not empty

↓

Get number of nodes at current level

↓

For each node at this level

↓

If first node at level

↓

Add node value to left view

↓

Add left child to queue if exists

↓

Add right child to queue if exists

↓

Repeat for next level

↓

End when queue empty

↓

Return collected left view values

We start from the root and use a queue to traverse level by level. For each level, we record the first node's value as the left view. We add children to the queue to process the next level.

Execution Sample

DSA C#

Queue<TreeNode> q = new Queue<TreeNode>();
q.Enqueue(root);
while(q.Count > 0) {
  int size = q.Count;
  for(int i=0; i<size; i++) {
    TreeNode node = q.Dequeue();
    if(i == 0) leftView.Add(node.val);
    if(node.left != null) q.Enqueue(node.left);
    if(node.right != null) q.Enqueue(node.right);
  }
}

This code uses a queue to do a level order traversal and collects the first node of each level as the left side view.

Execution Table

Step	Operation	Node Processed	Queue Before	Queue After	Left View Collected	Visual Tree State
1	Initialize queue with root	1	[]	[1]	[]	1 / \ 2 3 / \ \ 4 5 6
2	Process level 1, size=1	1	[1]	[]	[1]	1 / \ 2 3 / \ \ 4 5 6
3	Enqueue left child 2	1	[]	[2]	[1]	1 / \ 2 3 / \ \ 4 5 6
4	Enqueue right child 3	1	[2]	[2,3]	[1]	1 / \ 2 3 / \ \ 4 5 6
5	Process level 2, size=2	2	[2,3]	[3]	[1,2]	1 / \ 2 3 / \ \ 4 5 6
6	Enqueue left child 4	2	[3]	[3,4]	[1,2]	1 / \ 2 3 / \ \ 4 5 6
7	Enqueue right child 5	2	[3,4]	[3,4,5]	[1,2]	1 / \ 2 3 / \ \ 4 5 6
8	Process node 3	3	[3,4,5]	[4,5]	[1,2]	1 / \ 2 3 / \ \ 4 5 6
9	Enqueue right child 6	3	[4,5]	[4,5,6]	[1,2]	1 / \ 2 3 / \ \ 4 5 6
10	Process level 3, size=3	4	[4,5,6]	[5,6]	[1,2,4]	1 / \ 2 3 / \ \ 4 5 6
11	Node 4 has no children	4	[5,6]	[5,6]	[1,2,4]	1 / \ 2 3 / \ \ 4 5 6
12	Process node 5	5	[5,6]	[6]	[1,2,4]	1 / \ 2 3 / \ \ 4 5 6
13	Node 5 has no children	5	[6]	[6]	[1,2,4]	1 / \ 2 3 / \ \ 4 5 6
14	Process node 6	6	[6]	[]	[1,2,4]	1 / \ 2 3 / \ \ 4 5 6
15	Node 6 has no children	6	[]	[]	[1,2,4]	1 / \ 2 3 / \ \ 4 5 6
16	Queue empty, end	-	[]	[]	[1,2,4]	1 / \ 2 3 / \ \ 4 5 6

💡 Queue is empty, all levels processed, left view collected

Variable Tracker

Variable	Start	After Step 1	After Step 5	After Step 10	Final
Queue	[]	[1]	[3]	[5,6]	[]
Left View	[]	[1]	[1,2]	[1,2,4]	[1,2,4]
Current Node	null	1	2	4	null

Key Moments - 3 Insights

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

Because the first node processed at each level is the leftmost node visible from the left side. This is shown in execution_table rows 2, 5, and 10 where i == 0 triggers adding to left view.

Why do we use a queue for this traversal?

A queue helps us process nodes level by level in order. The execution_table shows the queue state before and after processing each node, ensuring we visit nodes in breadth-first order.

What happens if a node has no left child but has a right child?

The right child is still enqueued and processed at the next level. The left view will pick the first node at that level, which could be the right child if no left child exists. This is visible in steps 8 and 9 where node 3 has no left child but right child 6 is enqueued.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, which node is added to the left view?

A Node 1

B Node 3

C Node 2

D Node 4

💡 Hint

Check the 'Left View Collected' column at step 5 in execution_table

At which step does the queue become empty, ending the traversal?

A Step 14

B Step 16

C Step 15

D Step 10

💡 Hint

Look at the 'Queue After' column in execution_table for the empty queue

If the root node had no left child, which node would appear first in the left view?

A The root node itself

B The right child of the root

C The left child of the root's left child

D No nodes would be in the left view

💡 Hint

Recall that the root node is always the first node processed and added to left view at step 2

Concept Snapshot

Left Side View of Binary Tree:
- Use level order traversal with a queue
- For each level, add the first node's value to left view
- Enqueue left then right children
- Continue until queue is empty
- Result is nodes visible from left side

Full Transcript

To find the left side view of a binary tree, we start at the root and use a queue to traverse the tree level by level. At each level, we process all nodes and add the first node's value to the left view list. We add children nodes to the queue to process the next level. This continues until the queue is empty, meaning all levels are processed. The collected values represent the nodes visible from the left side of the tree.

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 only

Solution

1. Step 1: Understand the view perspective

   The left side view shows nodes visible when looking at the tree from the left side.

2. Step 2: Identify visible nodes

   Only the first node at each level from the left is visible in this view.

3. Final Answer:

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

4. Quick Check:

   Left side view = nodes seen from left [OK]

Hint: Think of standing on the left side and looking at the tree [OK]

Common Mistakes:

• Confusing left side view with right side view
• Thinking it shows all leaf nodes
• Assuming it shows nodes at the deepest level only

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

easy

A. Stack

B. Dictionary

C. Queue

D. List

Solution

1. Step 1: Identify traversal method

   Left side view is found by level order traversal, which processes nodes level by level.

2. Step 2: Choose data structure for level order

   A queue is used to hold nodes of each level in order for processing.

3. Final Answer:

   Queue -> Option C

4. Quick Check:

   Level order traversal uses queue [OK]

Hint: Use queue for level-by-level tree traversal [OK]

Common Mistakes:

• Using stack which is for depth-first traversal
• Choosing dictionary which stores key-value pairs
• Using list 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, 2, 4]

B. [1, 3, 5]

C. [4, 2, 1]

D. [1, 2, 5]

Solution

1. Step 1: Identify nodes visible from left side

   At level 1: node 1 is visible; level 2: node 2; level 3: node 4.

2. Step 2: List nodes in order of levels

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

3. Final Answer:

   [1, 2, 4] -> Option A

4. Quick Check:

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

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

Common Mistakes:

• Choosing right side nodes instead
• Including nodes not visible from left
• Reversing order of nodes

4. Consider this C# code snippet to get the left side view of a binary tree:

public IList<int> LeftSideView(TreeNode root) {
    var result = new List<int>();
    if (root == null) return result;
    var queue = new Queue<TreeNode>();
    queue.Enqueue(root);
    while (queue.Count > 0) {
        int size = queue.Count;
        for (int i = 0; i < size; i++) {
            var node = queue.Dequeue();
            if (i == 0) result.Add(node.val);
            if (node.left != null) queue.Enqueue(node.left);
            if (node.right != null) queue.Enqueue(node.right);
        }
    }
    return result;
}

What is the bug in this code?

medium

A. It misses the root node in the result

B. It uses a stack instead of a queue

C. It adds the rightmost node instead of leftmost

D. It correctly returns the left side view

Solution

1. Step 1: Analyze the traversal logic

   The code uses a queue for level order traversal and adds the first node at each level to result.

2. Step 2: Verify correctness of node selection

   Adding node when i == 0 ensures leftmost node at each level is added.

3. Final Answer:

   It correctly returns the left side view -> Option D

4. Quick Check:

   First node per level added = left side view [OK]

Hint: Check if first node at each level is added [OK]

Common Mistakes:

• Confusing queue with stack usage
• Adding last node instead of first
• Skipping root node

5. You want to find the left side view of a binary tree but only have access to a recursive preorder traversal method. How can you modify the recursion to get the left side view?

hard

A. Traverse left child before right, but record only leaf nodes

B. Traverse left child before right, and record the first node visited at each depth level

C. Traverse right child before left, and record all nodes at each level

D. Traverse right child before left, and record the last node visited at each depth level

Solution

1. Step 1: Understand preorder traversal order

   Preorder visits root, then left, then right child recursively.

2. Step 2: Record first node at each depth

   By visiting left child first, the first node at each depth is the leftmost node.

3. Step 3: Skip recording if depth already visited

   Only add node value if this is the first visit at that depth.

4. Final Answer:

   Traverse left child before right, and record the first node visited at each depth level -> Option B

5. Quick Check:

   Left-first preorder + first node per depth = left side view [OK]

Hint: Visit left child first and record first node at each depth [OK]

Common Mistakes:

• Visiting right child first loses leftmost nodes
• Recording all nodes instead of first per level
• Recording only leaf nodes misses intermediate nodes