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

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

1 / 4

seenresultdiscarded

depth 0 == len(result)=0, so record 1. Recurse right first.

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.