Here is solutions for Binary Tree Right Side View.

1. Understand the problem

• You are given the root of a binary tree.

• Return the values of the nodes that are visible when looking at the tree from the right side, from top to bottom.

2. Clarify constraints, asks 4 - 5 questions including edge cases.

1. What should we return if the tree is empty?

=> Return [].

1. Is the tree always balanced?

=> No, it can be skewed.

1. Can values be negative?

=> Yes.

1. Can there be duplicate values?

=> Yes.

1. Do we return node values or the nodes themselves?

=> Return values only.

3. Explore examples.

1. Example 1

Input:
    1
   / \
  2   3
   \   \
    5   4

Output: [1, 3, 4]

Explanation:

• Level 0 → see 1

• Level 1 → see 3

• Level 2 → see 4

1. Example 2

Input: [1, None, 3]
Output: [1, 3]

4. Brainstorm 2 - 3 solutions, naive solution first and optimize later. Explain the key idea of each solution.

4.1. BFS / Level Order (Naive & Clear) - Time O(N), Space O(N/2)

• Idea:

  • Traverse level by level.
  • For each level, take the last node.
  • Append to the result.

• Time: O(N)

• Space: O(N/2)

4.2. DFS (Optimized Space by Depth Tracking) - Time O(H), Space O(H)

• Idea:

  • Do preorder DFS: root → right → left.

  • The first node you visit at each depth is the rightmost node.

  • Track depth and only add when depth == len(result).

• Time: O(H)

• Space: O(H)

5. Implement solutions.

5.1. Depth First Search - Time O(H), Space O(H)

Idea:

• Do preorder DFS: root → right → left.

• The first node you visit at each depth is the rightmost node.

• Track depth and only add when depth == len(result).

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

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

            # First time we reach this depth
            if depth == len(res):
                res.append(node.val)

            dfs(node.right, depth + 1)
            dfs(node.left, depth + 1)

        dfs(root, 0)
        return res

• Time: O(H)

• Space: O(H)

5.2. BFS (Level Order) - Time O(N), Space O(N / 2)

from collections import deque
from typing import Optional, List

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

        res = []
        q = deque([root])

        while q:
            level_size = len(q)

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

                # If it's the last node in this level
                if i == level_size - 1:
                    res.append(node.val)

                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)

        return res

• Time: O(N)

• Space: O(N / 2)

6. Dry run testcases.

    1
   / \
  2   3
   \   \
    5   4