Meta — Binary Tree Right Side View (BFS Level Order)

Problem Statement#

Given the root of a binary tree, imagine standing on the right side of it. Return the values of the nodes you can see ordered from top to bottom (the last node at each level).

Constraints:

• Number of nodes: 0 to 100
• -100 <= Node.val <= 100

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#

Binary Tree Right Side View (LeetCode 199) is a Meta interview staple that tests BFS level-order traversal — one of the most common tree operations. Meta uses this in their infrastructure for rendering hierarchical UI components and in Oculus for depth ordering of objects in a scene tree. If you can implement level-order BFS cleanly and extract the last element per level, you can solve dozens of tree variants.

The problem has two elegant solutions: BFS (natural level-by-level processing) and DFS (right-subtree-first traversal). BFS is more intuitive; DFS requires understanding that visiting right before left ensures the first node seen at each depth is the rightmost visible one.

Amazon, Google, and Microsoft ask this problem and its mirror (left side view). The pattern — tracking level boundaries during BFS — is reused in level order traversal, zigzag traversal, and average of levels problems.

The Core Insight#

BFS approach: Process the tree level by level using a queue. For each level, process all nodes in the current level. The last node processed at each level is the rightmost visible node.

DFS approach: Traverse right subtree before left subtree. Track the current depth. When you visit a node at a depth that has not been seen before, it is the rightmost visible node at that depth.

BFS is cleaner to reason about. DFS with right-first traversal is elegant and O(N) in space on a balanced tree (O(H) stack depth).

Visual Dry Run#

Tree:

    1
   / \
  2   3
   \    \
    5    4

Result: [1, 3, 4]

Solution (Optimal)#

from collections import deque
 
class Solution:
    # BFS approach
    def rightSideView(self, root) -> list:
        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
 
    # DFS approach (right-first)
    def rightSideViewDFS(self, root) -> list:
        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) {
    if (!root) return [];
 
    const result = [];
    const queue = [root];
 
    while (queue.length > 0) {
        const levelSize = queue.length;
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            if (i === levelSize - 1) result.push(node.val);
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
    }
 
    return result;
};

Time: O(N) — visit every node exactly once Space: O(W) for BFS where W is max tree width; O(H) for DFS where H is tree height

Common Mistakes#

• Not capturing level size before the inner loop — queue grows during iteration, breaking level boundaries
• Using queue.shift() in JavaScript in a tight loop — O(N^2) total; use a proper deque or index-based queue
• In DFS approach, visiting left before right — gives left side view instead of right
• Forgetting to handle empty tree (root is null) — return empty list, not crash
• Appending node.val on every level iteration instead of only the last one per level

Interview Tips#

• Start with BFS and mention DFS as an alternative — shows breadth of knowledge
• The level_size snapshot before the inner loop is the critical BFS pattern for any level-order problem
• DFS with right-first and depth == len(result) is elegant to explain verbally
• JavaScript's Array.shift() is O(N); mention you would use a deque in production
• Meta often follows up: "Now return the left side view" — just change right-first to left-first in DFS

Follow-up Questions#

• How do you get the left side view? — Same BFS (take first element per level) or DFS left-first
• How do you return all levels (full level order traversal)? — Append the entire level array to result
• How do you compute the average value at each level? — Accumulate sum during BFS level, divide by size
• What if the tree is very deep (100,000 levels)? — BFS is safe; DFS may stack overflow
• How do you compute zigzag level order traversal? — Alternate left-to-right and right-to-left per level

Key Takeaways#

• The BFS level order pattern requires capturing level_size = len(queue) before the inner loop
• The rightmost visible node at each level is the last node processed in each BFS level
• DFS right-first approach: first node at each new depth (depth == len(result)) is the rightmost visible
• Time is O(N) for both approaches; BFS space is O(W) (max width), DFS space is O(H) (height)
• Meta tests this to verify BFS level-order fluency — a pattern used in zigzag, averages, and level-max problems
• Left side view is the exact same problem with left/right priority swapped
• In JavaScript, avoid Array.shift() in BFS — use a pointer or proper deque for O(N) total shift cost