Right Side View of Binary Tree in DSA Rust

Mental Model

We want to see the nodes visible if we look at the tree from the right side, which means the rightmost node at each level.

Analogy: Imagine standing on the right side of a tall building with many floors and windows. You only see the windows on the right edge of each floor, not the ones behind or to the left.

      1
     / \
    2   3
     \   \
      5   4

Right side view: 1 -> 3 -> 4

Dry Run Walkthrough

Input: Binary tree: 1 -> 2, 3; 2 -> null, 5; 3 -> null, 4

Goal: Find the rightmost node at each level to form the right side view list

Step 1: Start level order traversal at root node 1

Level 0: [1↑]
Right side view so far: []

Why: We begin from the top level to find the rightmost node

Step 2: At level 0, only node 1 is present, add 1 to right side view

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

Why: Node 1 is the only and thus rightmost node at level 0

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

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

Why: We explore the next level to find its rightmost node

Step 4: At level 1, add rightmost node 3 to right side view

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

Why: Node 3 is the rightmost node at level 1

Step 5: Move to level 2, nodes 5 and 4 are present (children of 2 and 3)

Level 2: [5, 4↑]
Right side view so far: [1, 3]

Why: We continue to the next level to find the rightmost node

Step 6: At level 2, add rightmost node 4 to right side view

Level 2: [5, 4]
Right side view so far: [1, 3, 4]

Why: Node 4 is the rightmost node at level 2

Result:

Right side view list: [1, 3, 4]

Annotated Code

DSA Rust

use std::collections::VecDeque;

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

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

fn right_side_view(root: Option<Box<TreeNode>>) -> Vec<i32> {
    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();
            // Add left child to queue if exists
            if node.left.is_some() {
                queue.push_back(node.left.as_ref().unwrap().clone());
            }
            // Add right child to queue if exists
            if node.right.is_some() {
                queue.push_back(node.right.as_ref().unwrap().clone());
            }
            // If this is the last node in the current level, add its value
            if i == level_size - 1 {
                result.push(node.val);
            }
        }
    }
    result
}

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

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

    let view = right_side_view(Some(root));
    for val in view {
        print!("{} ", val);
    }
    println!();
}

queue.push_back(root.unwrap());

Initialize queue with root node to start level order traversal

while !queue.is_empty() {

Process nodes level by level until queue is empty

let level_size = queue.len();

Record number of nodes at current level

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

Remove node from front of queue to process

if node.left.is_some() { queue.push_back(node.left.as_ref().unwrap().clone()); }

Add left child to queue for next level

if node.right.is_some() { queue.push_back(node.right.as_ref().unwrap().clone()); }

Add right child to queue for next level

if i == level_size - 1 { result.push(node.val); }

Add value of rightmost node at this level to result

Output

1 3 4 

Complexity Analysis

Time: O(n) because we visit each node exactly once during level order traversal

Space: O(n) because in the worst case the queue holds all nodes at the largest level

vs Alternative: Compared to DFS approach, BFS naturally processes nodes level by level making it straightforward to identify rightmost nodes

Edge Cases

Empty tree (root is None)

Returns empty list since there are no nodes

DSA Rust

if root.is_none() { return result; }

Tree with only root node

Returns list with single root value

DSA Rust

queue.push_back(root.unwrap());

Tree where some nodes have only left or only right child

Still correctly identifies rightmost nodes at each level

DSA Rust

if node.left.is_some() { queue.push_back(node.left.as_ref().unwrap().clone()); } if node.right.is_some() { queue.push_back(node.right.as_ref().unwrap().clone()); }

When to Use This Pattern

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

Common Mistakes

Mistake: Adding the first node at each level instead of the last node
Fix: Add the node only when processing the last node in the current level (i == level_size - 1)

Mistake: Using preorder or inorder traversal which does not process nodes level by level
Fix: Use BFS (level order traversal) to access nodes level-wise

Summary

Finds the rightmost node at each level of a binary tree to show the right side view.

Use when you need to see the tree from the right side or get the last node visible at each depth.

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

Practice

1. What does the "Right Side View of Binary Tree" represent?

easy

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

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

C. All leaf nodes of the binary tree

D. All nodes at the deepest level of the tree

Solution

1. Step 1: Understand the view perspective

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

2. Step 2: Differentiate from other views

   Unlike left side or leaf views, it only includes the rightmost nodes at each level.

3. Final Answer:

   Nodes visible when the tree is viewed from the right side -> Option A

4. Quick Check:

   Right side view = rightmost nodes [OK]

Hint: Right side view shows rightmost nodes at each level [OK]

Common Mistakes:

• Confusing right side view with left side view
• Including all leaf nodes instead of rightmost nodes
• Thinking it shows all nodes at the deepest level

2. Which Rust code snippet correctly declares a binary tree node struct for the right side view problem?

easy

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

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

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

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

Solution

1. Step 1: Check ownership and optional children

   Rust needs Option for nullable child nodes with ownership.

2. Step 2: Validate correct struct syntax

   Option allows recursive tree structure safely.

3. Final Answer:

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

4. Quick Check:

   Use Option for children [OK]

Hint: Use Option for nullable child nodes [OK]

Common Mistakes:

• Using direct TreeNode type causing infinite size error
• Using references without lifetimes
• Using Option<TreeNode> without Box causing compile error

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

    1
   / \
  2   3
   \   \
    5   4

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

medium

A. [1, 2, 4]

B. [1, 2, 5]

C. [1, 3, 4]

D. [1, 3, 5]

Solution

1. Step 1: Identify rightmost nodes at each level

   Level 0: 1, Level 1: 3 (right child), Level 2: 4 (right child of 3)

2. Step 2: Collect these nodes in order

   Right side view vector is [1, 3, 4]

3. Final Answer:

   [1, 3, 4] -> Option C

4. Quick Check:

   Rightmost nodes per level = [1, 3, 4] [OK]

Hint: Pick rightmost node at each tree level [OK]

Common Mistakes:

• Choosing left child nodes instead of rightmost
• Including nodes not visible from right side
• Mixing order of nodes in output

4. Given this Rust function snippet for right side view, what is the bug?

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

medium

A. The function returns the left side view, not right side

B. Queue should be a linked list, not a vector

C. The loop should iterate backwards

D. Using unwrap() consumes the Option, causing ownership errors

Solution

1. Step 1: Analyze use of unwrap() on Option

   Calling unwrap() moves the value out, so subsequent uses cause ownership errors.

2. Step 2: Identify correct approach

   Use references or cloning to avoid moving ownership when pushing children into queue.

3. Final Answer:

   Using unwrap() consumes the Option, causing ownership errors -> Option D

4. Quick Check:

   unwrap() moves ownership, causing errors [OK]

Hint: Avoid unwrap() that moves ownership inside loops [OK]

Common Mistakes:

• Ignoring ownership rules in Rust
• Thinking vector is wrong data structure here
• Misunderstanding loop direction relevance

5. How would you modify a standard level order traversal in Rust to return the right side view of a binary tree efficiently?

hard

A. Traverse each level left to right, record last node's value per level

B. Traverse each level right to left, record first node's value per level

C. Traverse each level left to right, record first node's value per level

D. Traverse each level right to left, record last node's value per level

Solution

1. Step 1: Understand level order traversal direction

   Standard level order goes left to right per level.

2. Step 2: Identify which node to record

   Recording the last node at each level gives the rightmost visible node.

3. Final Answer:

   Traverse each level left to right, record last node's value per level -> Option A

4. Quick Check:

   Last node per level in left-to-right traversal = right side view [OK]

Hint: Record last node at each level in left-to-right traversal [OK]

Common Mistakes:

• Recording first node instead of last
• Changing traversal direction unnecessarily
• Confusing left and right side views