Binary Tree Right Side View

Standing to the right of the tree, the visible node at each depth is whichever node is rightmost at that depth. That can be found with BFS (take the last node of each level) or with a right-first DFS (the first node to reach a given depth wins, since right children are explored before left ones).

BFS (last node per level)

Time O(n)Space O(n)

Level-order traverse the tree; at each level, the last node processed is the rightmost one, and therefore the one visible from the right.

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def rightSideView(self, root: TreeNode | None) -> list[int]:
        if root is None:
            return []
        result = []
        queue = deque([root])
        while queue:
            level_size = len(queue)
            for i in range(level_size):
                node = queue.popleft()
                if i == level_size - 1:
                    result.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return result

Complexity: every node is enqueued and dequeued once → O(n) time. The queue can hold up to ~n/2 nodes at the widest level → O(n) space.

DFS (right child first)

OptimalTime O(n)Space O(h)

Visit right children before left children, and record a node’s value the first time its depth is reached. Since right is explored first, the first node seen at each depth is guaranteed to be the rightmost one at that depth.

class Solution:
    def rightSideView(self, root: TreeNode | None) -> list[int]:
        result = []

        def dfs(node: TreeNode | None, depth: int) -> None:
            if node is None:
                return
            if depth == len(result):
                result.append(node.val)
            dfs(node.right, depth + 1)
            dfs(node.left, depth + 1)

        dfs(root, 0)
        return result

Watch the depth slots: right-first DFS lets 3 claim depth 1 and 4 claim depth 2 before the left subtree (2, then 5) is ever reached, so the nodes that arrive late are skipped.

Depth to visible node

d0–

d1–

d2–

Visit order

1 / 7

currentresultdiscarded

Plan: right-first DFS. The first node to reach a depth is the rightmost there, so it claims that depth before the left subtree is explored.

Complexity: each node is visited exactly once → O(n) time, identical to BFS. Recursion depth tracks tree height → O(h) space, an improvement over BFS’s O(n) queue width on a wide, shallow tree.

Binary Tree Right Side View

BFS (last node per level)

DFS (right child first)

More Trees practice