199. Binary Tree Right Side View

At a Glance

• Topic: Tree
• Pattern: Analyze Pattern
• Difficulty: Medium
• LeetCode: 199

Problem Statement

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

Example 1:

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

Output: [1,3,4]

Explanation:

Example 2:

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

Output: [1,3,4,5]

Explanation:

Example 3:

Input: root = [1,null,3]

Output: [1,3]

Example 4:

Input: root = []

Output: []

Constraints:

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

Approach & Solution Steps

• Brute force — full level order then take last of each level — O(n) time / O(n) space — fine, not “brute” in complexity.
• Better — BFS last-of-level — O(n) time / O(w) space — standard.
• Optimal (alternate) — O(n) time / O(h) stack — preorder DFS with depth index, right before left so first seen at depth wins.

Optimal JS Solution

class TreeNode {
  constructor(val = 0, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function rightSideView(root) {
  if (root === null) {
    return [];
  }
  const view = [];
  const queue = [root];
  while (queue.length > 0) {
    const levelSize = queue.length;
    for (let index = 0; index < levelSize; index++) {
      const node = queue.shift();
      if (index === levelSize - 1) {
        view.push(node.val);
      }
      if (node.left !== null) {
        queue.push(node.left);
      }
      if (node.right !== null) {
        queue.push(node.right);
      }
    }
  }
  return view;
}

Edge Cases & Pitfalls

• Always consider empty or null inputs.
• Watch out for off-by-one index errors.