Right Side View of Binary Tree in DSA Java

Mental Model

We want to see the nodes visible when looking 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; you only see the windows on the right edge of each floor, not the ones behind.

       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 (level 0)

Queue: [1]
Right side view: []

Why: We begin from the root to explore each level

Step 2: Process level 0: dequeue 1, enqueue children 2 and 3; record 1 as rightmost at level 0

Queue: [2, 3]
Right side view: [1]

Why: 1 is the only node at level 0, so it's the rightmost

Step 3: Process level 1: dequeue 2, enqueue 5; dequeue 3, enqueue 4; record 3 as rightmost at level 1

Queue: [5, 4]
Right side view: [1, 3]

Why: 3 is the last node processed at level 1, so it's the rightmost

Step 4: Process level 2: dequeue 5, no children; dequeue 4, no children; record 4 as rightmost at level 2

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

Why: 4 is the last node at level 2, so it's the rightmost

Result:

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

Annotated Code

DSA Java

import java.util.*;

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

public class RightSideView {
    public static List<Integer> rightSideView(TreeNode root) {
        List<Integer> rightView = new ArrayList<>();
        if (root == null) return rightView;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                // Add children for next level
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
                // If last node in this level, add to right view
                if (i == levelSize - 1) rightView.add(node.val);
            }
        }
        return rightView;
    }

    public static void main(String[] args) {
        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);

        List<Integer> result = rightSideView(root);
        for (int val : result) {
            System.out.print(val + " ");
        }
    }
}

queue.offer(root);

Start BFS from root node

int levelSize = queue.size();

Get number of nodes at current level

TreeNode node = queue.poll();

Remove node from queue to process

if (node.left != null) queue.offer(node.left);

Add left child to queue for next level

if (node.right != null) queue.offer(node.right);

Add right child to queue for next level

if (i == levelSize - 1) rightView.add(node.val);

Add last node of level to right side view

Output

1 3 4 

Complexity Analysis

Time: O(n) because we visit each node exactly once during BFS

Space: O(w) where w is the maximum width of the tree due to queue storage

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

Edge Cases

Empty tree (root is null)

Returns empty list immediately

DSA Java

if (root == null) return rightView;

Tree with only one node

Returns list with that single node value

DSA Java

queue.offer(root);

Tree where all nodes only have left children

Right side view is all nodes since each level has only one node

DSA Java

if (node.left != null) queue.offer(node.left);

When to Use This Pattern

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

Common Mistakes

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

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

Summary

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

Use when you want to see which nodes are visible from the right side of the tree.

The key insight is to do a level order traversal and pick 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.

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