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.