LeetCode 199: Binary Tree Right Side View — Step-by-Step Visual Trace

#leetcode #python #algorithms #datastructures

Medium — Binary Tree | BFS | Queue | Tree Traversal

The Problem

Given the root of a binary tree, return the values of the nodes you can see ordered from top to bottom when looking at the tree from the right side.

Approach

Use level-order traversal (BFS) with a queue to process nodes level by level. For each level, only add the rightmost node's value to the result by checking if the current node is the last one processed in that level.

Time: O(n) · Space: O(w)

Code

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

        result = []
        queue = [root]

        while queue:
            level_size = len(queue)

            for i in range(level_size):
                node = queue.pop(0)
                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