Left Side View of Binary Tree in DSA Rust - 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 children to queue (left then right)

↓

Repeat for next level

↓

End when queue empty

↓

Return collected left side view

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 its children to the queue. Repeat until all levels are processed.

Execution Sample

DSA Rust

fn left_side_view(root: Option<&Box<TreeNode>>) -> Vec<i32> {
    let mut result = std::vec::Vec::new();
    let mut queue = std::collections::VecDeque::new();
    if let Some(node) = root {
        queue.push_back(node);
    }
    while !queue.is_empty() {
        let level_size = queue.len();
        for i in 0..level_size {
            let current = queue.pop_front().unwrap();
            if i == 0 {
                result.push(current.val);
            }
            if let Some(left) = current.left.as_ref() {
                queue.push_back(left);
            }
            if let Some(right) = current.right.as_ref() {
                queue.push_back(right);
            }
        }
    }
    result
}

This Rust function collects the left side view of a binary tree by level order traversal, adding the first node of each level to the result.

Execution Table

Step	Operation	Node Visited	Queue State (values)	Left View Collected	Visual Tree State
1	Initialize queue with root	1	[1]	[]	1 / \ 2 3 / \ 4 5
2	Process level 1, first node	1	[2, 3]	[1]	1 / \ 2 3 / \ 4 5
3	Add children of 1 to queue	-	[2, 3]	[1]	1 / \ 2 3 / \ 4 5
4	Process level 2, first node	2	[3, 4]	[1, 2]	1 / \ 2 3 / \ 4 5
5	Add children of 2 to queue	-	[3, 4]	[1, 2]	1 / \ 2 3 / \ 4 5
6	Process level 2, second node	3	[4, 5]	[1, 2]	1 / \ 2 3 / \ 4 5
7	Add children of 3 to queue	-	[4, 5]	[1, 2]	1 / \ 2 3 / \ 4 5
8	Process level 3, first node	4	[5]	[1, 2, 4]	1 / \ 2 3 / \ 4 5
9	Add children of 4 to queue	-	[5]	[1, 2, 4]	1 / \ 2 3 / \ 4 5
10	Process level 3, second node	5	[]	[1, 2, 4]	1 / \ 2 3 / \ 4 5
11	Add children of 5 to queue	-	[]	[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 3	After Step 5	After Step 7	After Step 9	After Step 11	Final
queue	[]	[1]	[2, 3]	[3, 4]	[4, 5]	[5]	[]	[]
left_view	[]	[]	[1]	[1, 2]	[1, 2]	[1, 2, 4]	[1, 2, 4]	[1, 2, 4]

Key Moments - 3 Insights

Why do we add the node value to the left view only when i == 0 in the loop?

Because i == 0 means this is the first node at the current level, which is the leftmost node visible from the left side. See execution_table rows 2, 4, and 8 where left view is updated.

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

Adding left child first ensures that when we process the next level, the leftmost nodes come out of the queue first, preserving the left side view order. See execution_table rows 3, 5, and 7.

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

The queue never gets initialized with a node, so the while loop never runs and the function returns an empty left view immediately. This is implied by the initial check in the code and the empty start state in variable_tracker.

Visual Quiz - 3 Questions

Look at the execution_table at Step 4. What is the queue state after visiting node 2?

A [3, 4]

B [4]

C [3]

D []

💡 Hint

Check the 'Queue State (values)' column at Step 4 in execution_table.

At which step does the left view first include the value 4?

A Step 10

B Step 6

C Step 8

D Step 12

💡 Hint

Look at the 'Left View Collected' column in execution_table to see when 4 is added.

If we changed the order of adding children to queue to right then left, how would the left view change?

A It would remain the same

B It would show the rightmost nodes instead

C It would show nodes in random order

D It would be empty

💡 Hint

Consider how queue order affects which nodes are processed first at each level (see key_moments about child addition order).

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 the left side view nodes in top-down order

Full Transcript

This visualization shows how to find the left side view of a binary tree by visiting nodes level by level. We start with the root node in a queue. For each level, we process all nodes, adding the first node's value to the left view. We add children nodes to the queue in left to right order to ensure the leftmost nodes are processed first at the next level. This continues until no nodes remain in the queue. The collected values form the left side view. The execution table tracks each step, showing the queue contents, the node visited, and the left view collected so far. The variable tracker shows how the queue and left view change after each step. Key moments clarify why we add only the first node of each level to the view and why child order matters. The quiz tests understanding of queue state and left view updates during traversal.

Practice

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

easy

A. All leaf nodes of the tree

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

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

D. Nodes at the deepest level of the tree

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 C

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
• Including all leaf nodes instead of first nodes per level
• Thinking it shows deepest nodes only

2. Which Rust code snippet correctly declares a binary tree node struct for left side view traversal?

easy

A. struct TreeNode { val: i32, left: TreeNode, right: TreeNode }

B. struct TreeNode { val: i32, left: Box<TreeNode>, right: Box<TreeNode> }

C. struct TreeNode { val: i32, left: &TreeNode, right: &TreeNode }

D. struct TreeNode { val: i32, left: Option, right: Option }

Solution

1. Step 1: Check ownership and optional children

   Rust binary trees use Option for nullable child nodes.

2. Step 2: Validate correct syntax

   Option allows for null or Some(child), which is correct for left and right.

3. Final Answer:

   struct TreeNode { val: i32, left: Option, right: Option } -> Option D

4. Quick Check:

   Use Option for nullable children [OK]

Hint: Use Option for child nodes in Rust [OK]

Common Mistakes:

• Using direct TreeNode type for children (causes infinite size)
• Using references without lifetimes
• Omitting Option for nullable children

3. What is the output of the left side view function for this tree?

    1
   / \
  2   3
   \   \
    5   4

Assuming the function returns a vector of node values visible from the left side.

medium

A. [1, 3, 4]

B. [1, 2, 5]

C. [1, 2, 4]

D. [1, 5, 4]

Solution

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

   Level 0: 1, Level 1: 2 (left child), Level 2: 5 (right child of 2)

2. Step 2: Collect visible nodes in order

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

3. Final Answer:

   [1, 2, 5] -> Option B

4. Quick Check:

   Left side nodes = [1, 2, 5] [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 Rust function snippet for left side view, what is the bug?

fn left_side_view(root: Option) -> Vec<i32> {
    let mut result = vec![];
    let mut queue = vec![root.unwrap()];
    while !queue.is_empty() {
        let level_size = queue.len();
        for i in 0..level_size {
            let node = queue.remove(0);
            if i == 0 {
                result.push(node.val);
            }
            if let Some(left) = node.left {
                queue.push(left);
            }
            if let Some(right) = node.right {
                queue.push(right);
            }
        }
    }
    result
}

medium

A. Calling unwrap() on root without checking if it is null

B. Using remove(0) on vector causes runtime error

C. Pushing right child before left child breaks left view order

D. Not returning the result vector at the end

Solution

1. Step 1: Check root unwrap usage

   Calling unwrap() on root without checking if it is null can cause panic if tree is empty.

2. Step 2: Confirm other parts are correct

   remove(0) works but is inefficient; order of pushing left then right is correct; result is returned.

3. Final Answer:

   Calling unwrap() on root without checking if it is null -> Option A

4. Quick Check:

   unwrap() on null causes panic [OK]

Hint: Check unwrap() calls for null before use [OK]

Common Mistakes:

• Ignoring unwrap panic possibility
• Thinking remove(0) causes error (just slow)
• Confusing child push order
• Missing return statement

5. You want to modify the left side view function to return the leftmost node values only for levels where the node value is even. Which approach is correct?

hard

A. Add a check inside the level loop: if i == 0 and node.val % 2 == 0, then push node.val to result

B. Push node.val for all nodes during traversal, then filter even values from result after traversal

C. Push node.val only if node.val is even, ignoring position in level

D. Push node.val if it is even and it is the rightmost node at the level

Solution

1. Step 1: Understand requirement for leftmost even nodes

   We want only the first node at each level if its value is even.

2. Step 2: Apply condition during traversal

   Check if i == 0 (leftmost) and node.val % 2 == 0 before pushing to result.

3. Final Answer:

   Add a check inside the level loop: if i == 0 and node.val % 2 == 0, then push node.val to result -> Option A

4. Quick Check:

   Filter leftmost nodes by even value during traversal [OK]

Hint: Check leftmost and even condition together inside loop [OK]

Common Mistakes:

• Filtering after traversal loses position info
• Ignoring leftmost position and filtering only by value
• Checking rightmost node instead of leftmost