199. Binary Tree Right Side View

At a Glance

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

Problem (one-liner)

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.

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

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

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)

Similar Problems

• 102. Binary Tree Level Order Traversal — full levels; this takes tail per level.
• 116. Populating Next Right Pointers in Each Node — connects same-level nodes.
• 1448. Count Good Nodes in Binary Tree — another depth-tracked tree walk.

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