Left Side View of Binary Tree in DSA Python - 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 in level

↓

Pop node from queue

↓

If first node in level, add to left view

↓

Add left child to queue if exists

↓

Add right child to queue if exists

↓

Repeat for all nodes in level

↓

Repeat for next level

↓

Return collected left view nodes

We visit the tree level by level from top to bottom, and at each level, we record the first node we see (the leftmost node). We use a queue to keep track of nodes to visit.

Execution Sample

DSA Python

def left_side_view(root):
    if not root:
        return []
    queue = [root]
    left_view = []
    while queue:
        level_length = len(queue)
        first_in_level = True
        for _ in range(level_length):
            node = queue.pop(0)
            if first_in_level:
                left_view.append(node.val)
                first_in_level = False
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    return left_view

This code collects the left side view nodes of a binary tree using level order traversal.

Execution Table

Step	Operation	Nodes in Queue	Pointer Changes	Visual State
1	Initialize queue with root (1)	[1]	queue = [1]	1 / \ 2 3
2	Start level 1, level_length=1	[1]	level_length=1	1 / \ 2 3
3	Pop node 1 (first in level)	[]	queue.pop(0)	1 / \ 2 3
4	Add node 1 to left view	-	left_view = [1]	Left view: [1]
5	Add left child 2 to queue	[2]	queue.append(2)	2 / \ 4 5
6	Add right child 3 to queue	[2,3]	queue.append(3)	3 / \ 6 7
7	Start level 2, level_length=2	[2,3]	level_length=2	2,3
8	Pop node 2 (first in level)	[3]	queue.pop(0)	2 / \ 4 5
9	Add node 2 to left view	-	left_view = [1,2]	Left view: [1,2]
10	Add left child 4 to queue	[3,4]	queue.append(4)	4
11	Add right child 5 to queue	[3,4,5]	queue.append(5)	5
12	Pop node 3	[4,5]	queue.pop(0)	3 / \ 6 7
13	Add left child 6 to queue	[4,5,6]	queue.append(6)	6
14	Add right child 7 to queue	[4,5,6,7]	queue.append(7)	7
15	Start level 3, level_length=4	[4,5,6,7]	level_length=4	4,5,6,7
16	Pop node 4 (first in level)	[5,6,7]	queue.pop(0)	4
17	Add node 4 to left view	-	left_view = [1,2,4]	Left view: [1,2,4]
18	Node 4 has no children	[5,6,7]	-	-
19	Pop node 5	[6,7]	queue.pop(0)	5
20	Node 5 has no children	[6,7]	-	-
21	Pop node 6	[7]	queue.pop(0)	6
22	Node 6 has no children	[7]	-	-
23	Pop node 7	[]	queue.pop(0)	7
24	Node 7 has no children	[]	-	-
25	Queue empty, end loop	[]	-	Left view collected: [1,2,4]

💡 Queue is empty, all levels processed

Variable Tracker

Variable	Start	After Step 1	After Step 6	After Step 14	After Step 24	Final
queue	[]	[1]	[2,3]	[4,5,6,7]	[]	[]
left_view	[]	[]	[1,2]	[1,2,4]	[1,2,4]	[1,2,4]
level_length	-	1	2	4	-	-

Key Moments - 3 Insights

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

Because the first node in the queue at each level is the leftmost node visible from the left side. This is shown in execution_table rows 4, 9, and 17 where the first node popped is added to left_view.

Why do we add children to the queue in left then right order?

Adding left child first ensures that at the next level, the leftmost nodes are processed first. This order is visible in execution_table rows 5-6 and 13-14.

What happens when a node has no children?

No new nodes are added to the queue, so the queue size decreases. This is shown in rows 18, 20, 22, and 24 where no children are added.

Visual Quiz - 3 Questions

Look at the execution_table at step 9, what is the left_view list?

A [1,2]

B [1,2,4]

C [1]

D []

💡 Hint

Check the 'Pointer Changes' column at step 9 in execution_table

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

A Step 24

B Step 25

C Step 23

D Step 18

💡 Hint

Look at the 'Nodes in Queue' column and 'exit_note' in execution_table

If we added right child before left child, how would the left_view change?

A It would remain the same

B It would be empty

C It would show rightmost nodes instead

D It would show nodes in reverse order

💡 Hint

Refer to key_moments about child addition order and left_view formation

Concept Snapshot

Left Side View of Binary Tree:
- Use level order traversal (BFS) with a queue
- At each level, record the first node (leftmost)
- Add left child before right child 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 visit nodes level by level from top to bottom. We use a queue to keep track of nodes to visit. At each level, we note the first node we pop from the queue because it is the leftmost visible node. We add its children to the queue, left child first, then right child, to maintain order. We repeat this until no nodes remain in the queue. The collected nodes form the left side view.

Practice

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

easy

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

B. Nodes at the deepest level of the tree

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 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 Python code snippets correctly initializes an empty list to store the left side view nodes?

easy

A. left_view = ()

B. left_view = {}

C. left_view = []

D. left_view = set()

Solution

1. Step 1: Identify the correct data structure

   We need a list to store nodes in order, so an empty list is best.

2. Step 2: Check syntax for list initialization

   Using square brackets [] creates an empty list in Python.

3. Final Answer:

   left_view = [] -> Option C

4. Quick Check:

   Empty list = [] [OK]

Hint: Use [] to create empty list for ordered nodes [OK]

Common Mistakes:

• Using {} which creates a dictionary, not a list
• Using () which creates a tuple, not a list
• Using set() which is unordered

3. What is the output of the following code that prints the left side view of the given binary tree?

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def left_side_view(root):
    result = []
    def dfs(node, level):
        if not node:
            return
        if level == len(result):
            result.append(node.val)
        dfs(node.left, level + 1)
        dfs(node.right, level + 1)
    dfs(root, 0)
    return result

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.right = Node(4)
root.right.right = Node(5)

print(left_side_view(root))

medium

A. [1, 2, 3]

B. [1, 2, 4]

C. [1, 3, 5]

D. [1, 4, 5]

Solution

1. Step 1: Trace DFS traversal and level checks

   At level 0, node 1 is added. At level 1, node 2 is added (left child). At level 2, node 4 is added (left child's right child).

2. Step 2: Confirm nodes added only once per level

   Right children at each level are ignored if left child exists at that level.

3. Final Answer:

   [1, 2, 4] -> Option B

4. Quick Check:

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

Hint: Add node if level equals result length during DFS [OK]

Common Mistakes:

• Adding right child nodes before left child nodes
• Appending nodes multiple times per level
• Confusing left and right children order

4. Find the error in the following code that attempts to print the left side view of a binary tree:

def left_side_view(root):
    result = []
    def dfs(node, level):
        if node is None:
            return
        if level < len(result):
            result.append(node.val)
        dfs(node.left, level + 1)
        dfs(node.right, level + 1)
    dfs(root, 0)
    return result

medium

A. The condition should be 'level == len(result)', not 'level < len(result)'

B. The base case should check 'if node' instead of 'if node is None'

C. The recursive calls should swap left and right children

D. The function should return 'result' inside the dfs function

Solution

1. Step 1: Analyze the condition for adding nodes

   The code uses 'level < len(result)' which is incorrect because nodes should be added only when level equals the current result length.

2. Step 2: Correct the condition to add nodes once per level

   Changing condition to 'level == len(result)' ensures only the first node at each level is added.

3. Final Answer:

   The condition should be 'level == len(result)', not 'level < len(result)' -> Option A

4. Quick Check:

   Use '==' to add first node per level [OK]

Hint: Add node only when level equals result length [OK]

Common Mistakes:

• Using '<' instead of '==' in condition
• Returning result inside recursive function
• Swapping left and right child calls unnecessarily

5. Given a binary tree, how would you modify the standard left side view algorithm to return the left side view nodes in reverse order (bottom to top)?

hard

A. Perform the usual left side view traversal, then reverse the result list before returning

B. Traverse the tree from right to left instead of left to right

C. Add nodes to the result list only if they are leaf nodes

D. Use a queue and perform level order traversal from right to left

Solution

1. Step 1: Perform standard left side view traversal

   Use DFS or BFS to collect the first node at each level from left to right.

2. Step 2: Reverse the collected list

   After traversal, reverse the list to get nodes from bottom to top.

3. Final Answer:

   Perform the usual left side view traversal, then reverse the result list before returning -> Option A

4. Quick Check:

   Reverse after left side view traversal [OK]

Hint: Reverse the left side view list after traversal [OK]

Common Mistakes:

• Changing traversal order instead of reversing result
• Collecting leaf nodes only
• Using right to left traversal which gives wrong nodes