Binary Tree Right Side View: what the camera sees depends on how you walk

Stand on the right side of a binary tree and look left. You see one node per level: whichever node sits furthest right at that depth. The problem asks for those values, top to bottom.

That is the whole problem. The question is not what the answer is -- it is which traversal structure gives you the rightmost node per level most cleanly.

In the tree above ([1,2,3,null,5,null,4]), the view from the right is [1, 3, 4]. Level 0 gives node 1 (only node). Level 1 gives node 3 (rightmost of 2 and 3). Level 2 gives node 4 (rightmost of 5 and 4).

The problem

Given the root of a binary tree, return the values of the nodes visible when standing on the right side of the tree, ordered from top to bottom — one node per level, whichever sits furthest right at that depth. Full statement: LeetCode 199.

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

What the constraints force

The node count is in [0, 100] and values in [-100, 100]. Neither bound creates any real pressure.

n <= 100 means a recursion depth of at most 100 (a completely skewed chain). Python's default limit is 1000. Stack overflow is not a concern here -- choosing iterative BFS over recursive DFS is a design preference, not a safety requirement.

-100 <= val <= 100 includes negatives and zero. The algorithm never compares values against each other; it only records them. The value range is completely irrelevant to correctness.

What the constraint does tell you: both BFS and DFS are O(n) in time, and neither beats the other on complexity class for n = 100. The choice between them comes down to how naturally the algorithm expresses the problem's structure.

Approach 1: BFS -- level snapshots with a queue

The direct translation of "rightmost node per level" is to process nodes level by level and record the last one each time. BFS does this literally.

The key mechanism: before processing a level, snapshot len(queue) as level_size. That count tells you exactly how many nodes belong to this level. Iterate through all of them, and the node at index level_size - 1 is the rightmost -- add its value to the result.

from collections import deque
from typing import List, Optional
 
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
 
        result = []
        queue = deque([root])
 
        while queue:
            level_size = len(queue)
 
            for i in range(level_size):
                node = queue.popleft()
 
                if i == level_size - 1:
                    result.append(node.val)
 
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
 
        return result

using System.Collections.Generic;
 
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
 
public class Solution {
    public IList<int> RightSideView(TreeNode root) {
        if (root == null) return new List<int>();
 
        var result = new List<int>();
        var queue = new Queue<TreeNode>();
        queue.Enqueue(root);
 
        while (queue.Count > 0) {
            int levelSize = queue.Count;
 
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.Dequeue();
 
                if (i == levelSize - 1) {
                    result.Add(node.val);
                }
 
                if (node.left != null) queue.Enqueue(node.left);
                if (node.right != null) queue.Enqueue(node.right);
            }
        }
 
        return result;
    }
}

Hand trace through [1,2,3,null,5,null,4]

Initial: queue = [1]

--- Level 0 (level_size = 1) ---
i=0: dequeue 1, i == level_size-1, result = [1]
     enqueue left=2, right=3
queue = [2, 3]

--- Level 1 (level_size = 2) ---
i=0: dequeue 2, i != level_size-1, skip
     enqueue left=null (skip), right=5
i=1: dequeue 3, i == level_size-1, result = [1, 3]
     enqueue left=null (skip), right=4
queue = [5, 4]

--- Level 2 (level_size = 2) ---
i=0: dequeue 5, i != level_size-1, skip
     no children
i=1: dequeue 4, i == level_size-1, result = [1, 3, 4]
     no children
queue = []

Return [1, 3, 4]

Time complexity: O(n). Every node is enqueued once and dequeued once. Each operation is O(1).

Space complexity: O(w) where w is the maximum width of the tree. The queue holds at most one full level at a time. In the worst case (a complete binary tree), the bottom level has n/2 nodes, making this O(n).

Approach 2: DFS -- claiming levels on first visit

DFS reaches the same answer through a completely different mental model. Instead of processing all nodes at a level together, DFS records the first node it encounters at each new depth. The trick: walk right children before left children. The first time you touch a given depth, you are guaranteed to be at the rightmost node that will ever be reached at that depth.

from typing import List, Optional
 
class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        result = []
 
        def dfs(node, depth):
            if not node:
                return
 
            # First time visiting this depth -> rightmost node seen so far
            if depth == len(result):
                result.append(node.val)
 
            # Right first -- critical for correctness
            dfs(node.right, depth + 1)
            dfs(node.left, depth + 1)
 
        dfs(root, 0)
        return result

using System.Collections.Generic;
 
public class Solution {
    public IList<int> RightSideView(TreeNode root) {
        var result = new List<int>();
        DFS(root, 0, result);
        return result;
    }
 
    private void DFS(TreeNode node, int depth, List<int> result) {
        if (node == null) return;
 
        // First time visiting this depth -> rightmost node seen so far
        if (depth == result.Count) {
            result.Add(node.val);
        }
 
        // Right first -- critical for correctness
        DFS(node.right, depth + 1, result);
        DFS(node.left, depth + 1, result);
    }
}

The condition depth == len(result) is the core insight. Because result is appended exactly once per depth level, len(result) equals the number of depths already claimed. When depth == len(result), the current depth is being visited for the first time.

Hand trace through [1,2,3,null,5,null,4]

dfs(1, depth=0): depth(0) == len([]) -> result = [1]
  dfs(3, depth=1): depth(1) == len([1]) -> result = [1, 3]
    dfs(4, depth=2): depth(2) == len([1,3]) -> result = [1, 3, 4]
      dfs(null, depth=3): return
      dfs(null, depth=3): return
    dfs(null, depth=2): return
  dfs(2, depth=1): depth(1) != len([1,3,4]) = 3 -> skip
    dfs(5, depth=2): depth(2) != len([1,3,4]) = 3 -> skip
      dfs(null, depth=3): return
      dfs(null, depth=3): return
    dfs(null, depth=2): return

Return [1, 3, 4]

Node 2 and node 5 are visited but their values are skipped -- depth 1 and depth 2 are already claimed. This is the DFS version of "we already have a rightmost node for this level."

Time complexity: O(n). Every node is visited exactly once.

Space complexity: O(h) where h is the height of the tree. The call stack holds at most h frames. For a balanced tree, h = log n; for a skewed chain, h = n. This is better than BFS's O(w) for balanced trees (since log n < n/2), and similar or worse for skewed trees.

A case where they diverge: left-only subtrees

Consider [1,2,3,4] where node 3 has no children but node 2 has a left child (node 4):

BFS: Level 0 = [1], rightmost = 1. Level 1 = [2, 3], rightmost = 3. Level 2 = [4], rightmost = 4. Result: [1, 3, 4].

DFS (right-first): visits 1 (claims depth 0) -> 3 (claims depth 1) -> 2 (depth 1 already claimed, skip) -> 4 (claims depth 2). Result: [1, 3, 4].

Both correct. The interesting thing here is that node 4 is a left child, yet it appears in the right-side view because it is the only node at its depth. Neither algorithm cares about left vs. right in isolation -- only about being the sole or rightmost representative at a given depth.

Edge cases

Empty tree (root = null): BFS returns immediately before entering the loop. DFS's dfs(null, 0) hits the base case immediately. Both return [].

Single node: BFS enqueues the root, processes level 0 with level_size = 1, records it. DFS visits root at depth 0, records it, then recurses into two nulls. Both return [root.val].

Completely left-skewed tree ([1,2,null,3,null,4]): Every level has exactly one node -- the leftmost. BFS processes each level and finds level_size = 1 every time, so it records every node. DFS walks right (null at each level) first, finds nothing, then walks left -- but depth is still unclaimed, so it records the left child. The view from the right is the entire spine of nodes. Both handle it correctly.

Completely right-skewed tree: Mirror of the above. BFS records the single node at each level. DFS walks straight down the right spine, claiming each depth in sequence. Identical results, but DFS is cleaner here -- it never touches a null right child unless there is no right child.

Trees with negative values (val = -50): the algorithm records values, never compares them against zero or any threshold. Negatives are not special.

Comparison table

For n = 100, the difference is negligible. For larger trees (imagining the same problem at n = 10^5), DFS saves real memory on balanced inputs.

Which one I would ship

I reach for DFS in an interview. The depth == len(result) condition is non-obvious on first read, but once you see it, the whole solution is five lines of Python with no imports. There is no queue to manage, no level_size snapshot to remember, no off-by-one risk at the loop boundary.

BFS is the pedagogically cleaner answer because "rightmost node per level" maps directly to "last node dequeued per BFS batch." If you are explaining the problem to someone encountering level-order traversal for the first time, BFS is the better teaching vehicle. It requires no clever insight -- just a clean level-by-level loop.

But if you are writing production code or if the interviewer asks for the most concise version: DFS. Right-first traversal and the depth == len(result) guard express the solution in a form that is hard to misread once you know the pattern.

The underlying pattern: level-indexed result construction

The DFS approach here belongs to a pattern I think of as level-indexed result construction: instead of grouping nodes at a level together (as BFS does), you use the size of the result list as a counter of claimed levels, and you ensure each level is claimed exactly once by controlling traversal order.

This pattern generalizes. Any problem where you want "one thing per level" and can control traversal order can use it. The trade-off is that BFS expresses level membership naturally -- you get all nodes at a level in the queue at once -- while DFS requires you to trust that a specific traversal order ensures the right node is claimed first.

Where this fits and what comes next

This is problem 11 in the trees series. The earlier entries established the core traversal primitives -- maximum depth (recursion on height), invert binary tree (structural mutation), level order traversal (BFS loop), same tree (paired traversal). Binary Tree Right Side View is the first problem in the series where the output is deliberately partial: you see the tree but only a slice of it. The algorithm has to selectively record.

Binary Tree Level Order Traversal (102) is the direct predecessor. There, you record all nodes per level. Here, you record only the last. If 102 is comfortable, 199 adds exactly one filtering decision on top of it.

Find Bottom Left Tree Value (513) is the mirror: instead of the last node per level, you want the first node at the deepest level. DFS would walk left-first; BFS would take the first node of the deepest batch.

Binary Tree Zigzag Level Order Traversal (103) extends the level-order pattern further: alternate between left-to-right and right-to-left collection at each depth. The BFS frame from this problem handles it with a direction flag.

Populating Next Right Pointers in Each Node (116) converts the level-grouping insight into a structural one: link same-level nodes into a linked list. The same BFS level snapshot -- level_size = len(queue) -- is the mechanism.