DSA problem
Binary Tree Right Side View
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. A node is visible from the right if it is the rightmost node at its depth — any other node at the same depth that lies to its left is obscured by it.
The natural insight is that the right-side view is exactly the last value seen at each level when we traverse the tree level by level from left to right. So a standard BFS already collects each level's values in left-to-right order; the rightmost value of that level is simply the last element of the per-level list.
A small optimisation avoids building the full per-level list at all: while dequeuing the level_size nodes of the current level, simply record the value of the LAST one (i.e. the node dequeued at iteration level_size - 1). This trims the per-level memory to a single integer.
An alternative DFS approach traverses the tree right-first and records a node's value the first time the DFS reaches a new depth (depth equals the current result length). Both run in O(n) time. BFS uses O(w) extra space; DFS uses O(h) recursion stack. Since this problem belongs to the level-order pattern, the canonical solution we present here is BFS.
Examples
root = [1,2,3,null,5,null,4][1,3,4]root = [1,null,3][1,3]root = [][]Constraints
- The number of nodes in the tree is in the range [0, 100].
- -100 <= Node.val <= 100
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.