Binary Tree Right Side View (LC 199)

Pattern: BFS — Level-by-Level Processing (or DFS with depth / right-first)
Difficulty: Medium
Key Concept: At each depth, the rightmost node (in left-to-right order) is what you see from the right side

Problem Statement

Given the root of a binary tree, return the values of the nodes you can see when you look at the tree from the right side, ordered from top to bottom.

Input: TreeNode root.
Output: List<Integer> — one value per level: the rightmost node at that level (in standard level-order left-to-right listing).

Example (tree [1,2,3,null,5,null,4]):

Level 0: [1] → rightmost 1
Level 1: [2, 3] → rightmost 3
Level 2: [5, 4] → rightmost 4

Output: [1, 3, 4].

1. Algorithm & Pseudocode

BFS approach

function rightSideView(root):
    if root is null:
        return empty list

    answer = empty list
    queue = queue with root

    while queue is not empty:
        levelSize = queue.size()

        for i from 0 to levelSize - 1:
            node = dequeue
            if i == levelSize - 1:
                append node.val to answer    // last node in this level
            enqueue children left then right (if non-null)

    return answer

DFS approach (optional optimal variant)

function dfs(node, depth):
    if node is null: return
    if depth == answer.size():
        answer.add(node.val)    // first node visited at this depth (if we go right first)
    dfs(node.right, depth + 1)
    dfs(node.left, depth + 1)

Brute force: BFS, build List<Integer> per level, then answer.add(level.get(level.size() - 1)) — extra work storing full levels.

Optimal BFS: Same loop as LC 102, but only record node.val when i == levelSize - 1.

2. Step-by-Step Analysis (Beginner-Friendly)

What does “right side” mean here? It is not “only follow node.right pointers.” A node can be visible from the right if it is the rightmost among all nodes at its depth (e.g., 5 is not in the answer for the sample because 4 is farther right on that row).
Why does “last node in the BFS inner loop” work? You dequeue level k in left-to-right order. The last dequeue of that batch is exactly the rightmost node at that depth.
Why i == levelSize - 1? The inner index i runs 0 … levelSize-1. The final iteration sees the rightmost node of the current level.
DFS trick: If you recurse right child before left, the first time you reach a new depth is at the rightmost node of that depth. Then if (depth == answer.size()) answer.add(node.val) is equivalent to the BFS “last of level” rule.
BFS vs DFS here: BFS stops naturally per level. DFS is also O(n) and uses O(h) stack (height h). BFS uses O(w) queue. Both are standard solutions.

3. The Dry Run

Tree [1,2,3,null,5,null,4]:

BFS — we show i, node.val, whether we append to answer, and queue after each dequeue (enqueue children in order left, right).

Step	`levelSize`	`i`	`node.val`	Append to `answer`?	`answer`	`queue` after this dequeue (then enqueue)
Init	—	—	—	—	`[]`	`[1]`
L0	1	0	1	Yes (last of level)	`[1]`	`[2,3]`
L1 start	2	0	2	No	`[1]`	`[3,5]`
L1	2	1	3	Yes	`[1,3]`	`[5,4]`
L2 start	2	0	5	No	`[1,3]`	`[4]`
L2	2	1	4	Yes	`[1,3,4]`	`[]`

Final answer: [1, 3, 4].

4. Java Solution

Brute Force

Build full levels, then take the last element of each. Time: O(n). Space: O(n) for storing every value in intermediate level lists (plus queue).

import java.util.*;

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

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

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<Integer> level = new ArrayList<>(levelSize);

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

        return answer;
    }
}

Optimal

BFS — only record the last node per level. Time: O(n). Space: O(w) for queue.

import java.util.*;

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

        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();
                if (i == levelSize - 1) {
                    answer.add(node.val);
                }
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }

        return answer;
    }
}

DFS optimal (right-first): Time O(n), Space O(h) recursion stack.

import java.util.*;

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

    private void dfs(TreeNode node, int depth, List<Integer> answer) {
        if (node == null) {
            return;
        }
        if (depth == answer.size()) {
            answer.add(node.val);
        }
        dfs(node.right, depth + 1, answer);
        dfs(node.left, depth + 1, answer);
    }
}

5. The “Java vs. Others” Edge

The condition i == levelSize - 1 reads clearly in Java, C++, and Python BFS loops; Java’s Queue interface with LinkedList is the usual LeetCode idiom.
DFS: answer.size() acting as “current number of recorded depths” is a classic pattern; must recurse right then left so the first visit at each depth is the rightmost visible node.
Pitfall: Confusing “right side view” with “always take node.right” — that fails whenever the rightmost visible node is under the left subtree (your dry run with 5 and 4 shows why).
C++: same i == levelSize - 1 check; Python: same with collections.deque.

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	O(n)	O(n)	Stores every node per level then takes last
Optimal BFS	O(n)	O(w)	Only stores one int per level in answer; queue width w
Optimal DFS	O(n)	O(h)	h = height; O(n) worst skewed tree

n = number of nodes.