54.Binary Tree Right Side View

MediumTrees · 9/15

Problem

Given the root of a binary tree, imagine standing on its right side. Return the values of the nodes you can see, ordered from top to bottom.

On each level you see exactly one node: the rightmost node of that level. Note that this node is not always a right child — if a level's right side is empty, a node from a left branch becomes visible.

Examples

Input:  root = [1,2,3,null,5,null,4]
Output: [1,3,4]

Input:  root = [1,2,3,4,null,null,null,5]
Output: [1,3,4,5]
Explanation: Levels 3 and 4 only exist under the left child 2, so 4 and 5 are visible.

Input:  root = []
Output: []

Constraints

The number of nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100

💡 Key Insight

The answer is "the last node of every level". A BFS that processes one level per round can record the last node polled in each round. Alternatively, a DFS that visits right before left reaches the rightmost node of each depth first, so the first node seen at every new depth is the visible one.

Full Level Order, Then Take Last

TimeO(n)SpaceO(n)

Intuition

Reuse the standard level order traversal to build every level as a list, then read off the last element of each list. Correct and simple, but it stores every value even though only one per level is needed.

Algorithm

Run BFS and build levels, a list of per-level value lists.
For each level in levels, append level.get(level.size() - 1) to the result.

Visualization

root = [1,2,3,null,5,null,4]

levels = [[1], [2, 3], [5, 4]]
last of each -> [1, 3, 4]

Code

java

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<List<Integer>> levels = new ArrayList<>();
        if (root != null) {
            Deque<TreeNode> queue = new ArrayDeque<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                int size = queue.size();
                List<Integer> level = new ArrayList<>();
                for (int i = 0; i < size; 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);
                }
                levels.add(level);
            }
        }
        List<Integer> result = new ArrayList<>();
        for (List<Integer> level : levels) {
            result.add(level.get(level.size() - 1)); // rightmost value
        }
        return result;
    }
}

Complexity

Time: O(n) — BFS plus one pass over the levels.
Space: O(n) — every value is stored in levels.

DFS, Right Child First

TimeO(n)SpaceO(h)

Intuition

Traverse with DFS but go right before left, carrying the current depth. The first node we reach at any depth is the rightmost one on that level. We detect "first time at this depth" with depth == result.size().

Algorithm

dfs(node, depth): if node is null, return.
If depth == result.size(), append node.val (first visit to this depth).
dfs(node.right, depth + 1), then dfs(node.left, depth + 1).

Visualization

root = [1,2,3,4,null,null,null,5]

visit 1 (d0) -> new depth -> [1]
visit 3 (d1) -> new depth -> [1,3]
visit 2 (d1) -> depth 1 already seen
visit 4 (d2) -> new depth -> [1,3,4]
visit 5 (d3) -> new depth -> [1,3,4,5]

Code

java

import java.util.ArrayList;
import java.util.List;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        dfs(root, 0, result);
        return result;
    }

    private void dfs(TreeNode node, int depth, List<Integer> result) {
        if (node == null) {
            return;
        }
        if (depth == result.size()) {
            result.add(node.val); // first (rightmost) node on this level
        }
        dfs(node.right, depth + 1, result); // right side first
        dfs(node.left, depth + 1, result);
    }
}

Complexity

Time: O(n) — every node is visited once.
Space: O(h) — recursion depth (excluding output).

BFS, Last Node per LevelOptimal

TimeO(n)SpaceO(w)

Intuition

Run level-by-level BFS, but keep nothing except the value of the last node polled in each round. Since children are enqueued left then right, the last node of a round is the rightmost node of that level.

Algorithm

If root is null, return [].
Enqueue root.
While the queue is not empty:
- size = queue.size().
- Poll size nodes, enqueuing children (left, then right). When i == size - 1, append that node's value.
Return the result.

Dry Run

flowchart TD
    N1["1 (level 0, last -> seen)"] --> N2["2"]
    N1 --> N3["3 (level 1, last -> seen)"]
    N2 --> N4["4 (level 2, only node -> seen)"]
    N4 --> N5["5 (level 3, only node -> seen)"]

round 1: queue [1]     -> last = 1
round 2: queue [2, 3]  -> last = 3
round 3: queue [4]     -> last = 4
round 4: queue [5]     -> last = 5
answer: [1, 3, 4, 5]

Code

java

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        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 (i == size - 1) {
                    result.add(node.val); // rightmost node of this level
                }
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }
        return result;
    }
}

Complexity

Time: O(n) — each node is enqueued and polled once.
Space: O(w) — the queue holds at most one level.

Complexity Comparison

Approach	Time	Space
Full Level Order, Then Take Last	O(n)	O(n)
DFS, Right Child First	O(n)	O(h)
BFS, Last Node per Level	O(n)	O(w)

Common Pitfalls

Only following right pointers from the root — this misses nodes like 4 and 5 in example 2 that are visible because the right side is shorter.
In the DFS version, visiting left before right records the leftmost node of each level instead.
In BFS, enqueuing right before left while still taking the last polled node gives the left view.
Forgetting the empty-tree case.