Binary Tree Right Side View — LC 199 BFS and DFS Patterns Interview Guide

Problem Statement#

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

Constraints:

• Number of nodes is in range 0 to 100
• Node values fit in 32-bit signed integer range
• Tree may be empty

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

Input:  root = [1,null,3]
Output: [1,3]

Why This Problem Matters#

LeetCode 199 Binary Tree Right Side View is a Medium that shows up in Amazon, Meta, Google, Apple, and Bloomberg loops. It is interesting because it has two equally valid optimal solutions — BFS-by-level and DFS-right-first — and interviewers often ask candidates to discuss both.

The problem tests level-aware tree traversal. A common trap is assuming the right view equals "the rightmost path" (just keep going right) — that is wrong, because if the right subtree is shorter, deeper left-subtree nodes become visible. The correct mental model is: at every depth, the rightmost node visible at that depth is in the view.

For senior interviews, the DFS variant is preferred because it uses O(h) call-stack space versus O(w) BFS queue space, where h is height and w is max width. On skewed trees this matters; on balanced trees they tie.

The Core Insight#

BFS approach: traverse level by level using a queue. The last node dequeued at each level is the rightmost visible node — append its value to the result.

DFS approach: preorder-with-right-first. Visit root, then right subtree, then left subtree, while tracking depth. The first time we reach a new depth, that node is the rightmost at that depth (because we visited right before left at every ancestor). Push it to the result.

The DFS variant is elegant because the invariant "first node seen at depth d is the rightmost at depth d" follows from visiting right before left at every recursion step. Both approaches are O(n) time; pick based on space preference.

Visual Dry Run#

Tree: root=1, 1.right=3, 1.left=2, 2.right=5, 3.right=4.

Visiting right-first guarantees the first hit at each depth is the rightmost.

Solution (Optimal)#

class Solution:
    def rightSideView(self, root):
        result = []
 
        def dfs(node, depth):
            if not node:
                return
            if depth == len(result):
                result.append(node.val)
            dfs(node.right, depth + 1)
            dfs(node.left, depth + 1)
 
        dfs(root, 0)
        return result

var rightSideView = function(root) {
    const result = [];
 
    const dfs = (node, depth) => {
        if (!node) return;
        if (depth === result.length) {
            result.push(node.val);
        }
        dfs(node.right, depth + 1);
        dfs(node.left, depth + 1);
    };
 
    dfs(root, 0);
    return result;
};

Time: O(n) — every node is visited exactly once. Space: O(h) — recursion stack proportional to tree height; O(log n) balanced, O(n) skewed.

Common Mistakes#

• Assuming the right view is "always go right" — wrong when the right subtree is shorter than the left
• BFS approach forgetting to read the last node before clearing the level
• DFS approach visiting left first — first node seen at a depth becomes leftmost, not rightmost
• Using result[depth] = node.val to overwrite instead of checking depth == len(result) — works but does extra writes
• Off-by-one in depth tracking, missing the root at depth 0

Interview Tips#

• Sketch a tree where the left subtree is taller than the right to dispel the "rightmost path" misconception
• Mention both BFS and DFS approaches; pick DFS for O(h) stack vs O(w) queue tradeoff if asked
• The mirror problem — left side view — is identical with dfs(node.left, ...) first
• Total nodes are bounded but skewed trees still hit O(n) recursion depth

Follow-up Questions#

• Left side view — flip the recursion order, visit left before right
• Bottom view of a binary tree — track column index, BFS, last value per column
• Top view — track column index, BFS, first value per column
• Vertical order traversal LC 987 — generalizes to all columns

Key Takeaways#

• LeetCode 199 Binary Tree Right Side View is Medium difficulty, frequently asked at Amazon, Meta, Google, and Apple
• Time complexity is O(n); BFS uses O(w) queue space, DFS uses O(h) stack space
• DFS visits right child before left child, pushing the first node seen at each new depth
• BFS variant takes the last node dequeued per level
• The view is depth-keyed, not "rightmost path" — taller left subtree contributes deeper nodes
• Mirror logic (visit left first) gives the left side view with no other changes
• Same depth-tracking pattern extends to top view, bottom view, and vertical order traversal