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

↓

Count nodes at current level

↓

For each node at this level

↓

If first node at level

↓

Add node value to left view

↓

Add children to queue

↓

Repeat for next level

↓

End when queue empty

↓

Return left side view list

We start from the root and use a queue to visit nodes level by level. For each level, we record the first node's value as part of the left side view, then add all children to the queue to process the next level.

Execution Sample

DSA C

void leftSideView(Node* root) {
  if (!root) return;
  queue<Node*> q;
  q.push(root);
  while (!q.empty()) {
    int n = q.size();
    for (int i = 0; i < n; i++) {
      Node* curr = q.front(); q.pop();
      if (i == 0) printf("%d ", curr->val);
      if (curr->left) q.push(curr->left);
      if (curr->right) q.push(curr->right);
    }
  }
}

This code prints the left side view of a binary tree by printing the first node at each level during a level order traversal.

Execution Table

Step	Operation	Current Node	Queue State	Left View Collected	Visual Tree State
1	Initialize queue with root	1	[1]	[]	1 / \ 2 3 / \ 4 5
2	Process level 1, n=1	1	[]	[1]	1 / \ 2 3 / \ 4 5
3	Add children of 1	1	[2,3]	[1]	1 / \ 2 3 / \ 4 5
4	Process level 2, n=2	2	[3]	[1,2]	1 / \ 2 3 / \ 4 5
5	Add children of 2	2	[3,4]	[1,2]	1 / \ 2 3 / \ 4 5
6	Process level 2, i=1	3	[4]	[1,2]	1 / \ 2 3 / \ 4 5
7	Add children of 3	3	[4,5]	[1,2]	1 / \ 2 3 / \ 4 5
8	Process level 3, n=2	4	[5]	[1,2,4]	1 / \ 2 3 / \ 4 5
9	Add children of 4	4	[5]	[1,2,4]	1 / \ 2 3 / \ 4 5
10	Process level 3, i=1	5	[]	[1,2,4]	1 / \ 2 3 / \ 4 5
11	Add children of 5	5	[]	[1,2,4]	1 / \ 2 3 / \ 4 5
12	Queue empty, end	-	[]	[1,2,4]	1 / \ 2 3 / \ 4 5

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

Variable Tracker

Variable	Start	After Step 1	After Step 4	After Step 8	Final
queue	[]	[1]	[3]	[5]	[]
current node	null	1	2	4	null
left view list	[]	[1]	[1,2]	[1,2,4]	[1,2,4]
level size (n)	0	1	2	2	0

Key Moments - 3 Insights

Why do we only add the first node's value at each level to the left view?

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

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 in the order needed to find the left side view, as shown by the queue states in execution_table.

What happens if the tree is empty (root is NULL)?

The queue starts empty, so the while loop never runs and the left view remains empty. This is the base case not shown here but important to handle.

Visual Quiz - 3 Questions

Look at the execution_table at Step 4. What is the left view collected so far?

A [1]

B [1,2]

C [1,3]

D []

💡 Hint

Check the 'Left View Collected' column at Step 4 in the execution_table.

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

A Step 12

B Step 11

C Step 10

D Step 9

💡 Hint

Look at the 'Queue State' column and find when it becomes [].

If the tree had an extra left child under node 4, when would it be added to the queue?

A After Step 10

B After Step 7

C After Step 9

D After Step 5

💡 Hint

Children are added immediately after processing their parent node, see Steps 5 and 9.

Concept Snapshot

Left Side View of Binary Tree:
- Use level order traversal with a queue
- For each level, record the first node's value
- Add children left then right to queue
- Continue until queue is empty
- Result is list of leftmost nodes per level

Full Transcript

To find the left side view of a binary tree, we start at the root and use a queue to visit nodes level by level. At each level, we record the first node's value because it is the leftmost visible node from that level. We add the left and right children of each node to the queue to process the next level. This continues until the queue is empty, meaning all levels have been processed. The collected values form the left side view. The execution table shows the queue state, current node, and left view collected at each step, helping visualize how the tree is traversed and the left view is built.

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 concept

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

2. Step 2: Differentiate from other views

   Right side view shows nodes from the right, leaf nodes are only the bottom nodes, and deepest level nodes are not necessarily visible from left.

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 [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 binary tree node structure for computing the left side view?

easy

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

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

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

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

Solution

1. Step 1: Check correct struct declaration

   typedef struct Node { int data; struct Node* left; struct Node* right; } Node; correctly declares a struct with pointers to left and right child nodes.

2. Step 2: Identify errors in other options

   struct Node { int data; Node* left; Node* right; }; typedef Node; misses struct keyword before Node pointers, C uses struct Node instead of pointers causing infinite size, D misses struct name for pointers.

3. Final Answer:

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

4. Quick Check:

   Correct struct with pointers = typedef struct Node { int data; struct Node* left; struct Node* right; } Node; [OK]

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

Common Mistakes:

• Using struct members instead of pointers causing infinite size
• Missing struct keyword before pointer types
• Incorrect typedef syntax

3. Given the following binary tree:

      1
     / \
    2   3
   /     \
  4       5

What is the left side view output printed by this C code?

void leftViewUtil(Node* root, int level, int* maxLevel) {
  if (!root) return;
  if (level > *maxLevel) {
    printf("%d ", 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. 1 3 5

B. 1 2 5

C. 1 2 4

D. 1 4 5

Solution

1. Step 1: Trace recursive calls and printing

   At level 1, print 1; level 2, print 2 (left child); level 3, print 4 (left child of 2). Right children at same levels are ignored since maxLevel is updated.

2. Step 2: Confirm output sequence

   Printed nodes are 1, 2, 4 in order with spaces.

3. Final Answer:

   1 2 4 -> Option C

4. Quick Check:

   Left side view nodes = 1 2 4 [OK]

Hint: Print first node at each level during preorder left-first traversal [OK]

Common Mistakes:

• Printing right child nodes before left
• Not updating maxLevel correctly
• Confusing left side view with right side view

4. Identify the bug in this C function intended to print the left side view of a binary tree:

void leftViewUtil(Node* root, int level, int* maxLevel) {
  if (root == NULL) return;
  if (level >= *maxLevel) {
    printf("%d ", root->data);
    *maxLevel = level;
  }
  leftViewUtil(root->left, level + 1, maxLevel);
  leftViewUtil(root->right, level + 1, maxLevel);
}

medium

A. The condition should be 'level > *maxLevel' instead of 'level >= *maxLevel'

B. The function should print after recursive calls, not before

C. The base case should check 'if (root != NULL)' instead of 'if (root == NULL)'

D. The maxLevel pointer should be passed by value, not by reference

Solution

1. Step 1: Analyze the condition for printing

   The condition 'level >= *maxLevel' causes printing nodes multiple times at the same level, which is incorrect.

2. Step 2: Correct condition usage

   It should be 'level > *maxLevel' to print only the first node encountered at each level.

3. Final Answer:

   The condition should be 'level > *maxLevel' instead of 'level >= *maxLevel' -> Option A

4. Quick Check:

   Use strict greater than for first node per level [OK]

Hint: Use '>' not '>=' to print only first node at each level [OK]

Common Mistakes:

• Using '>=' causes duplicate prints at same level
• Printing after recursion changes order
• Incorrect base case logic

5. You want to print the left side view of a binary tree using a queue for level order traversal. Which approach correctly achieves this?

1. Enqueue root
2. While queue not empty:
   a. Get number of nodes at current level (size)
   b. For i in 0 to size-1:
       - Dequeue node
       - If i == 0, print node data
       - Enqueue left child if exists
       - Enqueue right child if exists

What is the output for this tree?

      10
     /  \
    20   30
      \    \
      40    50

hard

A. 10 40 50

B. 10 30 50

C. 10 20 50

D. 10 20 40

Solution

1. Step 1: Perform level order traversal with printing first node per level

   Level 1: print 10; Level 2: print 20 (first node at level); Level 3: print 40 (first node at level).

2. Step 2: Confirm output sequence

   Nodes printed in order: 10 20 40 with spaces.

3. Final Answer:

   10 20 40 -> Option D

4. Quick Check:

   Left side view by level order = 10 20 40 [OK]

Hint: Print first node at each level during BFS traversal [OK]

Common Mistakes:

• Printing last node instead of first at each level
• Mixing left and right child enqueue order
• Not counting nodes per level correctly