Right Side View of Binary Tree in DSA Java - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the Right Side View of a binary tree?

The right side view of a binary tree is the set of nodes visible when the tree is seen from the right side. It includes the rightmost node at each level of the tree.

beginner

Which traversal method is commonly used to get the right side view of a binary tree?

Level order traversal (Breadth-First Search) is commonly used, where we visit nodes level by level and pick the last node at each level.

beginner

In the right side view algorithm, why do we pick the last node at each level?

Because the last node at each level is the rightmost node visible from the right side of the tree.

beginner

What data structure is useful to keep track of nodes at each level during the right side view traversal?

A queue is useful to perform level order traversal and keep track of nodes at each level.

intermediate

How does a recursive approach find the right side view of a binary tree?

It visits the right child first, then the left child, and records the first node visited at each depth level.

What node do you add to the right side view list at each level during BFS?

A The last node at the level

B The first node at the level

C The middle node at the level

D All nodes at the level

The last node at each level is the rightmost node visible from the right side.

Which data structure is best for level order traversal to find the right side view?

A Stack

B Queue

C HashMap

D ArrayList

A queue helps process nodes level by level in BFS.

In a recursive right side view, which child is visited first?

A Right child

B No children

C Both children simultaneously

D Left child

Visiting the right child first ensures the rightmost nodes are recorded first.

What is the output of the right side view for a tree with only left children?

A Only the leftmost nodes

B Only the root

C All nodes

D Only the rightmost nodes

Since there are no right children, the left children are visible from the right side.

Which of these is NOT a correct way to find the right side view?

A Level order traversal picking last node at each level

B Using a queue to track nodes level-wise

C Recursive DFS visiting right child first

D Inorder traversal collecting nodes

Inorder traversal does not guarantee rightmost nodes at each level.

Explain how to find the right side view of a binary tree using level order traversal.

Think about visiting nodes level by level and which node is visible from the right.

Describe a recursive method to get the right side view of a binary tree.

Focus on the order of visiting children and how to record nodes.

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