Right Side View of Binary Tree in DSA Java - Execution Trace

Concept Flow - Right Side View of Binary Tree

Start at root node

↓

Use queue for level order traversal

↓

For each level:

↓

Traverse all nodes

↓

Record last node's value at this level

↓

Add children to queue

↓

Repeat until queue empty

↓

Return collected right side view

We visit the tree level by level, always noting the last node at each level to get the right side view.

Execution Sample

DSA Java

public List<Integer> rightSideView(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            if (i == size - 1) result.add(node.val);
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }
    }
    return result;
}

This code collects the rightmost node's value at each level of the binary tree using a queue.

Execution Table

Step	Operation	Nodes in Queue	Pointer Changes	Visual State
1	Start with root node 1	[1]	queue = [1]	Tree: 1 Queue: [1]
2	Process level 1 (size=1)	[1]	poll 1	Visited: 1 Queue after poll: []
3	Add children of 1: 2, 3	[2,3]	queue = [2,3]	Tree: 1 / \ 2 3 Queue: [2,3] Right view: [1]
4	Process level 2 (size=2)	[2,3]	poll 2	Visited: 2 Queue after poll: [3]
5	Add children of 2: 5	[3,5]	queue = [3,5]	Tree: 1 / \ 2 3 / 5 Queue: [3,5] Right view: [1]
6	Process level 2 continued	[3,5]	poll 3	Visited: 3 Queue after poll: [5]
7	Add children of 3: none	[5]	queue = [5]	Tree: 1 / \ 2 3 / 5 Queue: [5] Right view: [1,3]
8	Process level 3 (size=1)	[5]	poll 5	Visited: 5 Queue after poll: []
9	Add children of 5: none	[]	queue = []	Tree: 1 / \ 2 3 / 5 Queue: [] Right view: [1,3,5]
10	Queue empty, end traversal	[]	stop	Final right side view: [1,3,5]

💡 Queue is empty, all levels processed, traversal ends.

Variable Tracker

Variable	Start	After Step 3	After Step 7	After Step 9	Final
queue	[]	[2,3]	[5]	[]	[]
result	[]	[1]	[1,3]	[1,3,5]	[1,3,5]
size	N/A	1	2	1	N/A
node	N/A	1	3	5	N/A

Key Moments - 3 Insights

Why do we add the node's value only when i == size - 1?

Because i == size - 1 means the node is the last in the current level, representing the rightmost visible node. See execution_table rows 2, 6, and 8 where the last node's value is added.

Why do we use a queue for traversal?

A queue helps us visit nodes level by level (breadth-first). This ensures we see all nodes at one level before moving to the next. Refer to execution_table steps 1-10 showing queue changes.

What happens if the tree is empty?

If root is null, the function returns an empty list immediately (see code line 'if (root == null) return result;'), so no traversal happens.

Visual Quiz - 3 Questions

Look at the execution_table at Step 7, what nodes are in the queue?

A [5]

B []

C [3,5]

D [2,3]

💡 Hint

Check the 'Nodes in Queue' column at Step 7 in execution_table.

At which step does the right side view list first get the value 3?

A Step 3

B Step 7

C Step 6

D Step 9

💡 Hint

Look at the 'Visual State' column and 'Right view' list updates in execution_table.

If the node 3 had a right child 4, how would the queue change after Step 7?

A [5]

B [4,5]

C [5,4]

D [3,5,4]

💡 Hint

Children are added left then right; see code lines adding children and queue updates in execution_table.

Concept Snapshot

Right Side View of Binary Tree:
- Use level order traversal with a queue
- For each level, add the last node's value to result
- Add left and right children to queue
- Continue until queue is empty
- Result shows visible nodes from right side

Full Transcript

This concept shows how to find the right side view of a binary tree by visiting nodes level by level. We use a queue to hold nodes of each level. At each level, we add the last node's value to the result list because it is visible from the right side. We add children nodes to the queue to process the next level. When the queue is empty, we have the full right side view. The example tree has nodes 1, 2, 3, and 5. The right side view is [1, 3, 5].

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.

2. Step 2: Differentiate from other views

   Unlike left side or leaf nodes, right side view includes the rightmost node 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
• Thinking it shows all leaf nodes
• Assuming it shows all nodes at deepest level

2. Which of the following Java method signatures is correct for a function that returns the right side view of a binary tree as a list of integers?

easy

A. public int rightSideView(TreeNode root)

B. public void rightSideView(TreeNode root)

C. public List<Integer> rightSideView(TreeNode root)

D. public TreeNode rightSideView(List<Integer> root)

Solution

1. Step 1: Identify return type for right side view

   The right side view returns a list of integers representing node values visible from the right side.

2. Step 2: Match method signature

   Method should return List<Integer> and accept TreeNode root as input.

3. Final Answer:

   public List<Integer> rightSideView(TreeNode root) -> Option C

4. Quick Check:

   Return list of integers = public List<Integer> rightSideView(TreeNode root) [OK]

Hint: Return a list of node values, input is root node [OK]

Common Mistakes:

• Returning int instead of list
• Using void return type
• Incorrect parameter types

3. What is the output of the following code snippet for the right side view of the binary tree?

class TreeNode {
  int val;
  TreeNode left, right;
  TreeNode(int x) { val = x; }
}

public List<Integer> rightSideView(TreeNode root) {
  List<Integer> result = new ArrayList<>();
  if (root == null) return result;
  Queue<TreeNode> queue = new LinkedList<>();
  queue.add(root);
  while (!queue.isEmpty()) {
    int size = queue.size();
    for (int i = 0; i < size; i++) {
      TreeNode node = queue.poll();
      if (node.left != null) queue.add(node.left);
      if (node.right != null) queue.add(node.right);
      if (i == size - 1) result.add(node.val);
    }
  }
  return result;
}

// Tree structure:
//      1
//     / \
//    2   3
//     \   \
//      5   4

TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.right = new TreeNode(5);
root.right.right = new TreeNode(4);
System.out.println(rightSideView(root));

medium

A. [1, 2, 4]

B. [1, 2, 5]

C. [1, 3, 5]

D. [1, 3, 4]

Solution

1. Step 1: Traverse level by level and identify rightmost nodes

   Level 1: Node 1 (only node), Level 2: Nodes 2 and 3, rightmost is 3, Level 3: Nodes 5 and 4, rightmost is 4.

2. Step 2: Collect rightmost nodes in order

   Right side view list is [1, 3, 4].

3. Final Answer:

   [1, 3, 4] -> Option D

4. Quick Check:

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

Hint: Pick last node at each level during BFS [OK]

Common Mistakes:

• Choosing leftmost nodes instead of rightmost
• Adding all nodes instead of only rightmost
• Confusing order of nodes

4. Identify the bug in the following code for computing the right side view of a binary tree:

public List<Integer> rightSideView(TreeNode root) {
  List<Integer> result = new ArrayList<>();
  if (root == null) return result;
  Queue<TreeNode> queue = new LinkedList<>();
  queue.add(root);
  while (!queue.isEmpty()) {
    int size = queue.size();
    for (int i = 0; i <= size; i++) {
      TreeNode node = queue.poll();
      if (node.left != null) queue.add(node.left);
      if (node.right != null) queue.add(node.right);
      if (i == size - 1) result.add(node.val);
    }
  }
  return result;
}

medium

A. The null check for root is missing

B. The for loop condition should be i < size, not i <= size

C. The queue should be a Stack instead of a Queue

D. The result list should be a Set to avoid duplicates

Solution

1. Step 1: Analyze the for loop condition

   The for loop runs from i = 0 to i <= size, which causes one extra iteration and poll from empty queue.

2. Step 2: Correct the loop boundary

   The loop should run i < size to process exactly 'size' nodes per level.

3. Final Answer:

   The for loop condition should be i < size, not i <= size -> Option B

4. Quick Check:

   Loop boundary off by one = The for loop condition should be i < size, not i <= size [OK]

Hint: Use i < size for loops over queue size [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Replacing queue with stack incorrectly
• Ignoring null root check
• Using Set instead of List unnecessarily

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

hard

A. All of the above approaches can achieve the reverse right side view

B. Traverse the tree from bottom to top using recursion and add rightmost nodes

C. Use a stack to store rightmost nodes during BFS and pop them to reverse order

D. Collect rightmost nodes top to bottom, then reverse the list before returning

Solution

1. Step 1: Understand the standard right side view

   Standard approach collects rightmost nodes level by level from top to bottom.

2. Step 2: Consider ways to reverse order

   We can reverse the collected list, use recursion bottom-up, or use a stack to reverse order after BFS.

3. Step 3: Confirm all methods are valid

   Each method correctly produces the right side view in reverse order.

4. Final Answer:

   All of the above approaches can achieve the reverse right side view -> Option A

5. Quick Check:

   Multiple valid methods = All of the above approaches can achieve the reverse right side view [OK]

Hint: Reverse collected list or use stack/recursion [OK]

Common Mistakes:

• Thinking only one method works
• Ignoring simple list reversal
• Confusing traversal order