Binary Tree Right Side View

Problem

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.

Example 1:

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

Example 2:

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

Example 3:

Input: root = []
Output: []

Constraints:

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

Solution

Approach: BFS (Level Order)

The key insight is to use level order traversal and take the last (rightmost) node at each level.

Implementation

from collections import deque

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []

        result = []
        queue = deque([root])

        while queue:
            level_size = len(queue)

            for i in range(level_size):
                node = queue.popleft()

                # Add rightmost node of this level
                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

Alternative (DFS):

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        result = []

        def dfs(node, depth):
            if not node:
                return

            # If visiting this depth for first time, add node
            if depth == len(result):
                result.append(node.val)

            # Visit right first to ensure rightmost node is added
            dfs(node.right, depth + 1)
            dfs(node.left, depth + 1)

        dfs(root, 0)
        return result

Complexity Analysis

Time Complexity: O(n), where n is the number of nodes. We visit each node once.
Space Complexity: O(w) for BFS where w is max width, O(h) for DFS where h is height.

Key Insights

Rightmost at Each Level: The right side view consists of the rightmost node at each level.
BFS Approach: Process level by level and take the last node at each level.
DFS Approach: Visit right children before left, and add the first node encountered at each depth.
Depth Tracking: In DFS, depth == len(result) means we’re visiting this depth for the first time.
Visibility: Even if a node doesn’t have a right child, we see the rightmost node at that level (could be from left subtree).