Binary Tree Right Side View

MediumTrees · BFS / DFS by Depth🧩 Tree BFS (Level Order)LeetCode #199 ↗Updated Oct 30, 2026

Problem

Picture yourself standing to the right of a binary tree. Return the values of the nodes you can see, from the top level down — that is, the last (rightmost) node of every level. A left-subtree node is visible if nothing at its depth lies to its right.

Input[1,2,3,null,5,null,4]Output[1,3,4]

Input[1,2,3,4]Output[1,3,4]

Input[]Output[]

0 ≤ nodes ≤ 100 · -100 ≤ Node.val ≤ 100

Try it yourself

Java

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

The answer has exactly one value per depth. Visit nodes so that the first node seen at each new depth is the rightmost one: a DFS that goes right before left does exactly that.

PatternTree BFS (Level Order)

Instinct The answer talks about levels, rows, depth order, "closest to the root" or what you see from a side? Queue the tree and process it one level at a time.

Memory hack Freeze the size, drain the row - read n = queue.size() before the loop and one level never bleeds into the next.

Open the Tree BFS (Level Order) guide →

Approaches

Brute ForceHeight + Rightmost Search per Depth

Time O(n · h)Space O(h)

For each depth d below the height, run a separate right-first DFS that returns the first node it meets at depth d. Correct, but the top of the tree is re-explored for every level.

Java

public List<Integer> rightSideView(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    int h = height(root);
    for (int d = 0; d < h; d++) res.add(rightmost(root, d).val);
    return res;
}
private int height(TreeNode node) {
    return node == null ? 0 : 1 + Math.max(height(node.left), height(node.right));
}
// first node reached at depth d, exploring right before left
private TreeNode rightmost(TreeNode node, int d) {
    if (node == null) return null;
    if (d == 0) return node;
    TreeNode r = rightmost(node.right, d - 1);
    return r != null ? r : rightmost(node.left, d - 1);
}

Easy to justify, but a skewed tree (h = n) makes it O(n²).

BetterBFS — Last Node of Each Level

Time O(n)Space O(w)

Standard level-order traversal with a size snapshot. Children are enqueued left then right, so the last node polled in each round is the rightmost one of that level. Queue holds at most the widest level w.

Java

public List<Integer> rightSideView(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) return res;
    Queue<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 (i == size - 1) res.add(node.val); // rightmost of this level
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
    }
    return res;
}

Linear and iterative; the queue can hold ~n/2 nodes on a full tree.

OptimalDFS — Right Child First

Time O(n)Space O(h)

Pre-order DFS visiting right before left, carrying depth. When depth == res.size() we have reached a new level for the first time, and right-first order guarantees this node is the rightmost — record it. Only the recursion stack (height h) is used.

Java

public List<Integer> rightSideView(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    dfs(root, 0, res);
    return res;
}
private void dfs(TreeNode node, int depth, List<Integer> res) {
    if (node == null) return;
    if (depth == res.size()) res.add(node.val); // first node at this depth
    dfs(node.right, depth + 1, res);
    dfs(node.left, depth + 1, res);
}

One pass, no queue; O(log n) space on balanced trees (O(n) only if skewed).

Pro tip

Swap the two recursive calls and you get the Left Side View for free.

At a glance

Level	Approach	Time	Space
Brute Force	Height + Rightmost Search per Depth	`O(n · h)`	`O(h)`
Better	BFS — Last Node of Each Level	`O(n)`	`O(w)`
Optimal	DFS — Right Child First	`O(n)`	`O(h)`

Common pitfalls

Following only right pointers — misses left nodes visible below a short right side.
BFS: recording the first node of each level instead of the last.
DFS: visiting left before right, so the leftmost node claims the depth.

Interview tips

Clarify with a tree whose left side is deeper (e.g. [1,2,3,4] → 4 is visible).
Rephrase as “last node of each level” — BFS then becomes obvious.
Offer the right-first DFS and compare O(h) vs O(w) space.

Pattern

One answer per depth → BFS with a level snapshot, or DFS with depth == res.size() as the “first visit” test.

My notes saved in this browser