Difficulty: MediumTrees

Binary Tree Right Side View

Problem in Plain English

Given the root of a binary tree, return the values visible when looking from the right side, which is exactly the rightmost node of each level from top to bottom.

Problem Statement

Given the root of a binary tree, imagine standing on its right side and return the values you can see from top to bottom.

Exactly one node per level is visible: the rightmost node at that depth, even when it sits in a left subtree.

Constraints

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

Examples

Example 1

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

Depth 0 contains 1; depth 1 contains 2 then 3; depth 2 contains 5 then 4. Taking the rightmost value from each depth gives [1,3,4].

Example 2

Input: root = [1,null,3]
Output: [1,3]

Each depth has only one node, so both 1 and 3 are visible.

Example 3

Input: root = []
Output: []

There are no levels in an empty tree, so the view is an empty list.

Example 4

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

Node 3 hides 2 at depth 1, but its subtree stops there. At depths 2 and 3, nodes 4 and 5 in the left subtree are the only existing nodes and remain visible.

Example 5

Input: root = [7,7,7,null,7]
Output: [7,7,7]

Visibility depends on position, not distinct values. Each depth contributes a 7, so repeated values must stay in the answer.

Intuition

The right side view chooses one node at each depth: the rightmost existing node, regardless of its value or whether its path follows right-child links. In Example 1, depth 2 contains 5 and 4, so 4 hides 5. Breadth-first search can take the last node of each left-to-right level; depth-first search can visit right children first and take the first node at each new depth. Both must still explore left subtrees, because those may extend below every node on the right.

Approaches

Level Order Last Node

Solution Details

Reveal Level Order Last Node: intuition, complexity, and code

Intuition

Breadth-first search visits one depth at a time in left-to-right order, so the last node of each level is visible from the right. Snapshot the current level size before adding children: those children belong to the next level. In Example 1, batches [1], [2,3] and [5,4] contribute 1, 3 and 4. A deque, or an array with a head index and per-level compaction, keeps queue operations linear overall.

Step-by-Step Logic

Return an empty list for an empty root. Otherwise enqueue the root and initialize result. Example 1 begins with queue [1] and result [].
Snapshot the number of pending nodes before processing a level. For the root the size is 1; remove 1, append it as the last node, and enqueue children 2 then 3.
Remove exactly the snapshotted number of nodes, recording only the final one and enqueuing left before right children. For size 2, removing 2 adds 5 but records nothing; removing 3 records 3 and adds 4.
Repeat for each next level. Queue [5,4] has size 2, so removing 5 records nothing and removing 4 appends 4. In JavaScript, clear each consumed queue slot and compact once after the level to release old references.
When no pending nodes remain, return result. Example 1 yields [1,3,4]; node values and child links have only been read.

Why It Works

At the start of each level, the pending queue contains exactly that level in left-to-right order. Initially this holds for the root alone. Processing precisely the snapshotted size removes all and only current-level nodes. Enqueuing each parent left child before its right child, with parents themselves processed left to right, establishes the same invariant for the next level. Therefore the final removed node in each batch is exactly the rightmost node at that depth. Appending its value yields one entry per depth in top-to-bottom order. Every existing child is enqueued, so a visible node in a deeper left subtree is included even when the right subtree has ended. An empty root has no levels and returns an empty list.

Dry Run

Level Order Last Node: variable states at each step
Event	levelSize	i	Pending queue after event	Last in level?	result before -> after
Initialize	not set	not set	[1]	pending	[] -> []
Snapshot depth 0	1	not set	[1]	pending	[] -> []
Remove 1; record it; enqueue 2 then 3	1	0	[2,3]	yes	[] -> [1]
Finish level; JS compacts consumed slots	1	loop ended	[2,3]	completed	[1] -> [1]
Snapshot depth 1	2	not set	[2,3]	pending	[1] -> [1]
Remove 2; enqueue 5	2	0	[3,5]	no	[1] -> [1]
Remove 3; record it; enqueue 4	2	1	[5,4]	yes	[1] -> [1,3]
Finish level; JS compacts consumed slots	2	loop ended	[5,4]	completed	[1,3] -> [1,3]
Snapshot depth 2	2	not set	[5,4]	pending	[1,3] -> [1,3]
Remove 5; no children	2	0	[4]	no	[1,3] -> [1,3]
Remove 4; record it; no children	2	1	[]	yes	[1,3] -> [1,3,4]
Finish level; JS compacts to []	2	loop ended	[]	completed	[1,3,4] -> [1,3,4]
Return result	finished	finished	[]	finished	return [1,3,4]

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(w)

Let n be the node count, h the number of levels, and w the maximum level width. Each node is enqueued and processed once. Java ArrayDeque and Python deque remove from the front in constant amortized time. JavaScript advances head instead of shifting, clears consumed references, and slices once per level; each next-level node is copied once, so total copying is O(n). Queue storage, including temporarily overlapping old and compacted arrays, is O(w): at most the current and next levels coexist. This is auxiliary space excluding the O(h) returned list; counting the output gives O(w + h), which is O(n) in the worst case. The empty tree uses constant working space and returns an empty list.

Code

Solution.java

1import java.util.ArrayDeque;2import java.util.ArrayList;3import java.util.List;4import java.util.Queue;5
6class TreeNode {7    int val;8    TreeNode left, right;9    TreeNode(int val) { this.val = val; }10    TreeNode(int val, TreeNode left, TreeNode right) {11        this.val = val; this.left = left; this.right = right;12    }13}14
15class Solution {16    public List<Integer> rightSideView(TreeNode root) {17        List<Integer> result = new ArrayList<>();18        if (root == null) return result;19        Queue<TreeNode> queue = new ArrayDeque<>();20        queue.offer(root);21        while (!queue.isEmpty()) {22            // Children join the next level, so freeze this level's boundary first.23            int levelSize = queue.size();24            for (int i = 0; i < levelSize; i++) {25                TreeNode node = queue.poll();26                if (i == levelSize - 1) result.add(node.val);27                // Parent order plus left-before-right preserves spatial order.28                if (node.left != null) queue.offer(node.left);29                if (node.right != null) queue.offer(node.right);30            }31        }32        return result;33    }34}

Hints

Hint 1

One node per level survives: the rightmost one at that depth.

Hint 2

In breadth-first order, the visible node is simply the last one dequeued in each level batch.

Hint 3

In depth-first order, always go right first and record the first node seen at each new depth.

Edge Cases

An empty tree returns []; a single node contributes its value once.
A left-only chain still shows every node: each level has only one candidate.
A left subtree extending below the right subtree contributes visible nodes at those deeper levels, as in [1,2,3,4,null,null,null,5].
Two nodes at the same depth with equal values still represent different positions; choose the rightmost node and do not deduplicate answer values.
Negative and zero values affect neither ordering nor visibility.
A 100-node chain gives 100 output values and maximum recursion depth; a broad tree instead maximizes breadth-first queue storage.

Common Mistakes and Interview Tips

Following only right-child links, missing deeper visible nodes in the left subtree.
Recording every node of a level or the first node in a left-first breadth-first queue instead of its last node.
Testing the changing queue size inside the loop, mixing children into their parent level.
Traversing left first while recording first arrivals, which produces the left side view.
Stopping DFS at an already-recorded depth instead of merely skipping its value, which loses deeper visible descendants.
Choosing the largest value at a level instead of the rightmost position, or deduplicating repeated values.
Using JavaScript shift for every removal, or keeping consumed array references forever while claiming width-bounded queue storage.
Keeping result as persistent solution state without clearing it between calls.

Key Takeaway

A per-level view is a traversal plus a selection rule: left-to-right BFS takes the last node, while right-first DFS takes the first node at each depth. Visit all subtrees even when the current depth already has a selected value, because deeper levels may still need an answer.