Binary Tree Right Side View

The problem description can be found in LeetCode.

Approach

Again, we have another example that perfectly adapts to DFS (like Binary Tree Level Order Traversal).

We will make a level order traversal and simply add the last one of the level in our result.

Solution

from collections import deque
from typing import Deque, List, Optional


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

        if root:
            queue.append(root)

        ans = []
        while queue:
            ans.append(queue[-1].val)

            for _ in range(len(queue)):
                node = queue.popleft()
                for child in [node.left, node.right]:
                    if child:
                        queue.append(child)

        return ans

Complexity

• Time: $O(n)$
• Space: $O(2^h)$

Where $n$ is the number of nodes in the tree. If our input is a perfect binary tree, the maximum number of nodes that could be in the queue are the ones in the last level, which is $2^h$, where $h$ is the height of the tree.