199 · Binary Tree Right Side View

Stand to the right of the tree and look along each level: what you can see is the last node BFS touches on that level, or equivalently, the first node a right-first DFS reaches at that depth.

1 — The problem

Return the values you'd see looking at the tree from the right side, top to bottom — one value per level, the rightmost node visible on that level. This is level order traversal (102) with a one-line change: instead of collecting the whole level, keep only its last element.

Approach	What "rightmost" means operationally	Time / space
BFS, last of each level	The last node dequeued during a level's size-snapshot loop — because children are enqueued left-to-right, that's always the rightmost.	O(n) / O(n)
DFS, right child first	Recurse right-before-left; the first node arriving at a new depth is the rightmost one, since every other path to that depth is explored later.	O(n) / O(h)

2 — Visualizing the BFS approach

Last node per level[1,2,3,null,5,null,4]interactive

Queue<TreeNode> q = new LinkedList<>();q.add(root);while (!q.isEmpty()) {    int sz = q.size();    for (int i = 0; i < sz; i++) {        TreeNode nd = q.poll();        if (i == sz - 1) result.add(nd.val);        if (nd.left  != null) q.add(nd.left);        if (nd.right != null) q.add(nd.right);    }}

Watch level 2: the queue at that point is [5, 3]. 5 is dequeued first and discarded from the answer; 3 is dequeued last and kept — even though 5 is visually "further right" in the picture, it's tucked behind node 2 from a right-side viewer's perspective, while 3 has nothing to its right at all. The condition i == sz - 1, not the node's on-screen position, is what defines "visible".

2.1 The DFS alternative

Recursing right-before-left gets the same answer from the opposite direction: the first time the recursion reaches a given depth, it must have come via the rightmost path, because every node that could hide a righter path (an unexplored right child somewhere higher up) is visited before we ever descend left.

Java 21Right-first DFS, four lines shorter than the BFS version.7 lines

void dfs(TreeNode nd, int depth, List<Integer> result) {
    if (nd == null) return;
    if (depth == result.size()) result.add(nd.val); // first arrival at this depth
    dfs(nd.right, depth + 1, result);
    dfs(nd.left,  depth + 1, result);
}

3 — Complexity and edge cases

Time: O(n), space: O(n) for BFS (queue holds a full level); O(h) call-stack space for the DFS version.
Empty tree: return an empty list.
A left-leaning tree with no right children at all (a straight line of left children) still produces one value per level — the lone node on each level is trivially both the first and last, so both approaches degenerate to plain root-to-leaf traversal.
Common bug: using the node's value comparison instead of its queue position to decide "rightmost" — position in the level order is what matters, not the node's own left/right lineage, exactly as node 5 vs node 3 demonstrates above.

4 — Reference implementation

Java 21BFS version, matching the visualizer.15 lines

public List<Integer> rightSideView(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;
    Queue<TreeNode> q = new LinkedList<>();
    q.add(root);
    while (!q.isEmpty()) {
        int sz = q.size();
        for (int i = 0; i < sz; i++) {
            TreeNode nd = q.poll();
            if (i == sz - 1) result.add(nd.val);
            if (nd.left  != null) q.add(nd.left);
            if (nd.right != null) q.add(nd.right);
        }
    }
    return result;
}