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

Concept Flow - Left Side View of Binary Tree

Start at root node

↓

Use queue for level order traversal

↓

For each level:

↓

Visit nodes left to right

↓

Record first node of level

↓

Add children to queue

↓

Repeat until queue empty

↓

Output collected left side nodes

Traverse the tree level by level, record the first node at each level to get the left side view.

Execution Sample

DSA C++

struct Node {
  int val;
  Node* left;
  Node* right;
};

vector<int> leftSideView(Node* root) {
  // BFS level order, record first node per level
}

This code collects the leftmost node at each level of the binary tree using a queue.

Execution Table

Step	Operation	Queue State	Visited Node	Left Side View List	Visual Tree State
1	Start: enqueue root (1)	[1]	None	[]	1 / \ 2 3 / \ \ 4 5 6
2	Process level 1: dequeue 1, record 1	[]	1	[1]	1 / \ 2 3 / \ \ 4 5 6
3	Enqueue children of 1: 2, 3	[2,3]	None	[1]	1 / \ 2 3 / \ \ 4 5 6
4	Process level 2: dequeue 2, record 2	[3]	2	[1,2]	1 / \ 2 3 / \ \ 4 5 6
5	Enqueue children of 2: 4, 5	[3,4,5]	None	[1,2]	1 / \ 2 3 / \ \ 4 5 6
6	Process level 2: dequeue 3, do not record	[4,5]	3	[1,2]	1 / \ 2 3 / \ \ 4 5 6
7	Enqueue child of 3: 6	[4,5,6]	None	[1,2]	1 / \ 2 3 / \ \ 4 5 6
8	Process level 3: dequeue 4, record 4	[5,6]	4	[1,2,4]	1 / \ 2 3 / \ \ 4 5 6
9	4 has no children to enqueue	[5,6]	None	[1,2,4]	1 / \ 2 3 / \ \ 4 5 6
10	Process level 3: dequeue 5, do not record	[6]	5	[1,2,4]	1 / \ 2 3 / \ \ 4 5 6
11	5 has no children	[6]	None	[1,2,4]	1 / \ 2 3 / \ \ 4 5 6
12	Process level 3: dequeue 6, do not record	[]	6	[1,2,4]	1 / \ 2 3 / \ \ 4 5 6
13	6 has no children	[]	None	[1,2,4]	1 / \ 2 3 / \ \ 4 5 6
14	Queue empty, traversal done	[]	None	[1,2,4]	1 / \ 2 3 / \ \ 4 5 6

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

Variable Tracker

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

Key Moments - 3 Insights

Why do we only record the first node at each level?

Because the first node visited at each level is the leftmost node visible from the left side. See execution_table rows 2, 4, and 8 where nodes 1, 2, and 4 are recorded.

Why do we continue processing other nodes at the same level after recording the first?

We need to enqueue all children of nodes at the current level to process the next level. The first node is recorded, but others are processed to add their children. See rows 6 and 10 where nodes 3 and 5 are processed but not recorded.

What happens if the tree is empty?

If the root is null, the queue starts empty and traversal ends immediately with an empty left side view list. This is implied by the exit condition in row 14.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, which node is recorded in the left side view list?

A Node 2

B Node 3

C Node 1

D Node 4

💡 Hint

Check the 'Left Side View List' column at step 4 in the execution_table.

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

A Step 10

B Step 12

C Step 14

D Step 8

💡 Hint

Look at the 'Queue State' column in the execution_table and find when it is [].

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

A [1, 3, 4]

B [1, 2, 5]

C [1, 2, 4]

D [1, 2, 6]

💡 Hint

Consider that without node 2's left child, the next leftmost node at level 3 would be node 5.

Concept Snapshot

Left Side View of Binary Tree:
- Traverse tree level by level (BFS).
- At each level, record the first node visited.
- Use a queue to track nodes per level.
- Enqueue children left to right.
- 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 do a level order traversal. At each level, we visit nodes from left to right. We record only the first node we visit at each level because that node is visible from the left side. We continue until all levels are processed and the queue is empty. The recorded nodes form the left side view list. This method ensures we see the leftmost nodes at every depth of the tree.

Practice

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

easy

A. Nodes at the deepest level of the tree

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

C. All leaf nodes of the tree

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

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 encountered 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 D

4. Quick Check:

   Left side view = nodes visible from left [OK]

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

Common Mistakes:

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

2. Which of the following C++ code snippets correctly declares a node structure for a binary tree used in left side view traversal?

easy

A. struct Node { int data; Node* left; Node* right; };

B. struct Node { int data; Node left; Node right; };

C. struct Node { int data; Node* left; int right; };

D. struct Node { int data; int left; int right; };

Solution

1. Step 1: Check pointer usage for child nodes

   Child nodes must be pointers to allow dynamic linking in a tree.

2. Step 2: Validate data types

   Data is int, left and right children are pointers to Node, matching correct binary tree node structure.

3. Final Answer:

   struct Node { int data; Node* left; Node* right; }; -> Option A

4. Quick Check:

   Use pointers for child nodes in tree struct [OK]

Hint: Use pointers for left and right child nodes in struct [OK]

Common Mistakes:

• Using Node instead of Node* for children
• Using int type for child nodes
• Omitting pointers causing infinite size error

3. Consider the following binary tree:

      1
     / \
    2   3
   / \   \
  4   5   6

What is the left side view output of this tree?

medium

A. [1, 3, 6]

B. [1, 2, 4]

C. [1, 2, 5]

D. [1, 2, 6]

Solution

1. Step 1: Identify nodes visible from left at each level

   Level 1: 1, Level 2: 2 (left child), Level 3: 4 (left child of 2)

2. Step 2: Collect nodes in order

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

3. Final Answer:

   [1, 2, 4] -> Option B

4. Quick Check:

   Left side view 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 nodes from different levels

4. The following C++ function is intended to print the left side view of a binary tree. What is the error?

void leftViewUtil(Node* root, int level, int &maxLevel) {
    if (!root) return;
    if (level > maxLevel) {
        cout << root->data << " ";
        maxLevel = level;
    }
    leftViewUtil(root->left, level + 1, maxLevel);
    leftViewUtil(root->right, level + 1, maxLevel);
}

void leftView(Node* root) {
    int maxLevel = 0;
    leftViewUtil(root, 1, maxLevel);
}

medium

A. The order of recursive calls should be right child first, then left child

B. maxLevel should be initialized to -1 instead of 0

C. No error; function correctly prints left side view

D. The function should print after both recursive calls

Solution

1. Step 1: Analyze traversal order and maxLevel usage

   The function visits left child first, then right child, printing first node at each level.

2. Step 2: Check initialization and printing logic

   maxLevel initialized to 0 and level starts at 1, so first level prints correctly; printing before recursion is correct.

3. Final Answer:

   No error; function correctly prints left side view -> Option C

4. Quick Check:

   Correct preorder traversal prints left view [OK]

Hint: Left child first recursion prints left view correctly [OK]

Common Mistakes:

• Changing recursion order breaks left view logic
• Incorrect maxLevel initialization causing missed nodes
• Printing after recursion misses first nodes

5. Given a binary tree where some levels have missing left children but have right children, which approach ensures correct left side view output?

hard

A. Traverse level order and pick first node at each level

B. Traverse preorder and print nodes only if left child exists

C. Traverse inorder and print nodes at odd levels

D. Traverse postorder and print leaf nodes only

Solution

1. Step 1: Understand problem with missing left children

   Left side view must include visible nodes even if left child is missing but right child exists.

2. Step 2: Choose traversal that captures first visible node per level

   Level order traversal visits nodes level by level, so picking first node at each level ensures correct left side view.

3. Final Answer:

   Traverse level order and pick first node at each level -> Option A

4. Quick Check:

   Level order first node per level = left side view [OK]

Hint: Use level order traversal, pick first node at each level [OK]

Common Mistakes:

• Ignoring right child when left child is missing
• Using preorder which may miss visible nodes
• Confusing inorder or postorder with left view logic