Binary Tree Right Side View

Why it belongs on this sheet

This is a nice traversal problem where order matters as much as the visited nodes.

Pattern

Capture the last node of each level

Approach

Run BFS level by level. The last node processed in each level is the one visible from the right side.

Java solution

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

class Solution {
  public List<Integer> rightSideView(TreeNode root) {
    List<Integer> answer = new ArrayList<>();
    if (root == null) {
      return answer;
    }

    Deque<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
      int size = queue.size();
      for (int i = 0; i < size; i++) {
        TreeNode node = queue.poll();
        if (node.left != null) {
          queue.offer(node.left);
        }
        if (node.right != null) {
          queue.offer(node.right);
        }
        if (i == size - 1) {
          answer.add(node.val);
        }
      }
    }

    return answer;
  }
}

Complexity

• Time: O(n)
• Space: O(n)

Interview note

Right-first DFS is another elegant version if you want to discuss alternatives.