Left Side View of Binary Tree in DSA Rust

Mental Model

We want to see the nodes visible when looking at the tree from the left side, which means the first node at each level.

Analogy: Imagine standing on the left side of a tall building and only seeing the first window on each floor from your view.

      1
     / \
    2   3
   / \   \
  4   5   6

Left side view: 1 -> 2 -> 4

Dry Run Walkthrough

Input: Binary tree: 1 with left child 2 and right child 3; 2 has children 4 and 5; 3 has right child 6

Goal: Find the leftmost node at each level to form the left side view list

Step 1: Start level order traversal at root node 1

Level 0: [1]
Left side view so far: [1]

Why: Root is always visible from the left side

Step 2: Move to level 1, nodes 2 and 3

Level 1: [2, 3]
Left side view so far: [1, 2]

Why: At level 1, node 2 is the first node visible from the left

Step 3: Move to level 2, nodes 4, 5, and 6

Level 2: [4, 5, 6]
Left side view so far: [1, 2, 4]

Why: At level 2, node 4 is the first node visible from the left

Result:

Left side view: 1 -> 2 -> 4

Annotated Code

DSA Rust

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug, Clone)]
struct TreeNode {
    val: i32,
    left: Option<Rc<RefCell<TreeNode>>>,
    right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    fn new(val: i32) -> Rc<RefCell<TreeNode>> {
        Rc::new(RefCell::new(TreeNode { val, left: None, right: None }))
    }
}

fn left_side_view(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
    use std::collections::VecDeque;
    let mut result = Vec::new();
    if root.is_none() {
        return result;
    }
    let mut queue = VecDeque::new();
    queue.push_back(root.unwrap());

    while !queue.is_empty() {
        let level_size = queue.len();
        for i in 0..level_size {
            let node = queue.pop_front().unwrap();
            if i == 0 {
                result.push(node.borrow().val); // first node at this level
            }
            if let Some(left) = &node.borrow().left {
                queue.push_back(left.clone()); // enqueue left child
            }
            if let Some(right) = &node.borrow().right {
                queue.push_back(right.clone()); // enqueue right child
            }
        }
    }
    result
}

fn main() {
    // Construct the tree:
    //       1
    //      / \
    //     2   3
    //    / \   \
    //   4   5   6
    let root = TreeNode::new(1);
    let node2 = TreeNode::new(2);
    let node3 = TreeNode::new(3);
    let node4 = TreeNode::new(4);
    let node5 = TreeNode::new(5);
    let node6 = TreeNode::new(6);

    root.borrow_mut().left = Some(node2.clone());
    root.borrow_mut().right = Some(node3.clone());
    node2.borrow_mut().left = Some(node4.clone());
    node2.borrow_mut().right = Some(node5.clone());
    node3.borrow_mut().right = Some(node6.clone());

    let view = left_side_view(Some(root));
    for val in view {
        print!("{} -> ", val);
    }
    print!("null\n");
}

if root.is_none() { return result; }

handle empty tree edge case

queue.push_back(root.unwrap());

start BFS with root node

let level_size = queue.len();

determine number of nodes at current level

for i in 0..level_size {

iterate over all nodes at this level

let node = queue.pop_front().unwrap();

process next node in queue

if i == 0 { result.push(node.borrow().val); }

record first node at this level for left side view

if let Some(left) = &node.borrow().left { queue.push_back(left.clone()); }

enqueue left child if exists

if let Some(right) = &node.borrow().right { queue.push_back(right.clone()); }

enqueue right child if exists

Output

1 -> 2 -> 4 -> null

Complexity Analysis

Time: O(n) because we visit each node exactly once during the breadth-first traversal

Space: O(w) where w is the maximum width of the tree, due to the queue storing nodes at each level

vs Alternative: Compared to a depth-first approach that tracks levels, BFS naturally processes nodes level by level, making it straightforward to pick the first node at each level

Edge Cases

Empty tree (root is None)

Returns an empty list since there are no nodes to view

DSA Rust

if root.is_none() { return result; }

Tree with only root node

Returns a list with only the root value

DSA Rust

queue.push_back(root.unwrap());

Tree where some nodes have only right children

Still correctly picks the first node at each level, which may be a right child if no left child exists

DSA Rust

if i == 0 { result.push(node.borrow().val); }

When to Use This Pattern

When asked to find the visible nodes from one side of a binary tree, use level order traversal and pick the first node at each level to get the side view.

Common Mistakes

Mistake: Collecting all nodes at each level instead of only the first node
Fix: Only add the node value to the result when processing the first node at each level (i == 0)

Mistake: Using depth-first traversal without tracking levels carefully
Fix: Use breadth-first traversal (queue) to process nodes level by level for simpler logic

Summary

Finds the first node visible at each level when looking at the tree from the left side.

Use it when you need to see the leftmost nodes of a binary tree level by level.

The key insight is to do a level order traversal and record only the first node at each level.

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