Binary Tree Right Side View

Problem

You are given the root of a binary tree. Imagine standing to the right of the tree and looking left. Return the values of the nodes you can see, ordered from top to bottom.

In other words, for each depth level of the tree, the visible node is the rightmost one at that level. Return one value per level.

Examples

Example 1

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

Level 0: 1. Level 1: nodes 2,3 — rightmost is 3. Level 2: nodes 5,4 — rightmost is 4.

Example 2

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

The root 1 has only a right child 3; both are visible from the right.

Example 3

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

Level 0: 1. Level 1: 2,3 → 3. Level 2: only node 4 (left child of 2), so it is the rightmost by default.

Constraints

• The number of nodes is in the range [0, 100].
• -100 <= Node.val <= 100
• An empty tree returns an empty list.

Think about it first

TL;DR

BFS taking the last node of each level (or right-first DFS recording the first node per depth) — O(n) time, O(n) space.

Approach 1 — BFS level order, keep the last of each level

The right-side view is the rightmost node of every level, so process the tree level by level and record the last node dequeued for each level. Breadth-first search (BFS) uses a queue to visit all nodes at depth d before any at depth d+1.

Example 1 as a tree; the shaded nodes 1, 3, 4 are what you see from the right:

graph TD
    A[1] --> B[2]
    A --> C[3]
    B --> D[5]
    C --> E[4]
    classDef visible fill:#bcd6f7,stroke:#2a4d69,color:#000;
    class A,C,E visible;

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional, List
from collections import deque


def rightSideView(root: Optional[TreeNode]) -> List[int]:
    if not root:
        return []
    view: List[int] = []
    queue = deque([root])
    while queue:
        level_size = len(queue)
        for i in range(level_size):
            node = queue.popleft()
            if i == level_size - 1:  # last node of this level
                view.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    return view

Walkthrough on Example 1 ([1,2,3,null,5,null,4]):

1. Queue [1], size 1. i = 0 is last → record 1. Enqueue 2, 3.
2. Queue [2,3], size 2. i = 0: node 2, enqueue its right child 5. i = 1: node 3 is last → record 3, enqueue its right child 4.
3. Queue [5,4], size 2. i = 0: node 5. i = 1: node 4 is last → record 4.
4. Result [1,3,4].

Complexity: O(n) time — every node enqueued and dequeued once. O(n) space for the queue (up to a full level, which can be ~n/2 nodes).

Approach 2 — DFS, right child first, one value per new depth

If you recurse into the right subtree before the left and record a node only the first time you reach a given depth, that first node is the rightmost at its level. This trades the queue for the recursion stack.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional, List


def rightSideView(root: Optional[TreeNode]) -> List[int]:
    view: List[int] = []

    def dfs(node: Optional[TreeNode], depth: int) -> None:
        if not node:
            return
        if depth == len(view):  # first node reached at this depth
            view.append(node.val)
        dfs(node.right, depth + 1)  # right before left
        dfs(node.left, depth + 1)

    dfs(root, 0)
    return view

Walkthrough on Example 3 ([1,2,3,4], where 4 is the left child of 2):

1. dfs(1, 0): len(view) == 0 == depth → record 1. Recurse right into 3, then left into 2.
2. dfs(3, 1): len(view) == 1 == depth → record 3. Node 3 has no children.
3. Back to dfs(2, 1): len(view) == 2 != 1 → skip (depth 1 already filled by 3). Recurse right (None), then left into 4.
4. dfs(4, 2): len(view) == 2 == depth → record 4.
5. Result [1,3,4].

Complexity: O(n) time, O(h) space for the recursion stack (h = height; O(n) worst case, O(log n) balanced).

Common pitfalls

• Recording the wrong node in BFS: the visible node is the last dequeued in the level (i == level_size - 1), not the first. Capturing level_size before the inner loop is essential — the queue grows as you enqueue children.
• DFS visiting left first: if you recurse left before right, the “first node at each depth” becomes the leftmost, giving the left-side view. The right-first order is what makes it work.
• A node with only a left child: its left child can still be the rightmost at its level (Example 3). Both approaches handle this — BFS because it is the last dequeued, DFS because no right-side node filled that depth first.
• Empty tree: return []; the BFS guard (if not root) and the DFS null check both cover it.

Pattern takeaway

“One node per level” problems (right/left view, level maxima, level averages) are natural fits for BFS with a captured level size. When you would rather avoid a queue, a DFS that fixes child order and gates writes on “first time at this depth” (depth == len(result)) achieves the same per-level selection using the call stack.