199. Binary Tree Right Side View

Quick Identifier

Topic: trees
Pattern: BFS
Difficulty: Medium
Companies: Amazon, Facebook, Bloomberg, Google, Microsoft
Frequency: High
LeetCode: 199

Quick Sights

Time Complexity: O(n) from the optimal approach.
Space Complexity: O(h) from the optimal approach.
Core Mechanism: Given the root of a binary tree, return the values of nodes you would see if you stood on the right side of the tree—one node per level, the rightmost visible at that depth.

Concept Explanation

Given the root of a binary tree, return the values of nodes you would see if you stood on the right side of the tree—one node per level, the rightmost visible at that depth.

State the invariant before coding: what partial result is already correct, what work remains, and what value or state each recursive/iterative step must preserve.

Recognition cues:

"Right side view" / rightmost per level
Same levels as level-order; take last (or first if traversing right-to-left)
Alternative DFS: visit right child before left, record first hit per depth

Study Pattern (SDE3+)

0-3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

This diagram shows the algorithm movement for this problem family.

Loading diagram…

Approaches

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 Solution

Go

package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func rightSideView(root *TreeNode) []int {
	if root == nil {
		return []int{}
	}
	view := []int{}
	queue := []*TreeNode{root}
	for len(queue) > 0 {
		levelSize := len(queue)
		for index := 0; index < levelSize; index++ {
			node := queue[0]
			queue = queue[1:]
			if index == levelSize-1 {
				view = append(view, node.Val)
			}
			if node.Left != nil {
				queue = append(queue, node.Left)
			}
			if node.Right != nil {
				queue = append(queue, node.Right)
			}
		}
	}
	return view
}

JavaScript

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;
}

Walkthrough

Tree: 1 / 2,3 / null,5,null,4 (example shape)

BFS levels:

Level 1: rightmost 1 → view [1]
Level 2: nodes 2,3 → rightmost 3
Level 3: from 2 comes 5; 3 may have 4 → order depends on enqueue; rightmost at depth 3 recorded last in that level

Invariant: when index == levelSize-1, you have dequeued the last node of that level in left-to-right order = visually rightmost among nodes present at that level.

Edge Cases

Only left spine visible if no right children → last per level may be leftmost node at that level’s far left chain—still “rightmost existing node” at the level
Single node

Pitfalls

DFS variant must process right before left if taking first-at-depth
Confusing “visible from right” with only following right pointers (not the same if left subtree is deeper)

Variants

Left side view → take first node each level in BFS or swap DFS order.
Diagonal view → different indexing.

Mind-Map Tags

#trees #bfs #rightmost #level-order #visibility