LeetCode 199: Binary Tree Right Side View

Problem Restatement

We are given the root of a binary tree.

Imagine standing on the right side of the tree. From that view, at each depth, only the rightmost node is visible.

We need to return the visible node values from top to bottom. The official problem asks for the values of nodes visible from the right side of the binary tree.

Input and Output

Example function shape:

def rightSideView(root: Optional[TreeNode]) -> list[int]:
    ...

Examples

Example 1:

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

Tree:

    1
   / \
  2   3
   \   \
    5   4

From the right side:

Output:

[1, 3, 4]

Example 2:

root = [1,null,3]

Tree:

1
 \
  3

Output:

[1, 3]

Example 3:

root = []

Output:

[]

First Thought: Process the Tree Level by Level

The right side view contains one node per level.

So we should traverse the tree level by level.

For each level, the answer should include the last node on that level when nodes are read from left to right.

This is exactly what breadth-first search gives us.

Key Insight

During BFS, the queue contains all nodes of the current level.

If we process exactly level_size nodes, then the last node processed at that level is the rightmost node.

For example:

level nodes = [2, 3]

The rightmost node is 3.

So while processing the level, when the index is:

i == level_size - 1

we add that node’s value to the answer.

Algorithm

1. If root is None, return an empty list.
2. Put root into a queue.
3. While the queue is not empty:
   • Read the current queue length. This is the number of nodes at the current level.
   • Pop exactly that many nodes.
   • Add children for the next level.
   • When processing the last node of the current level, append its value to the answer.
4. Return the answer.

Correctness

BFS processes nodes by level.

At the start of each outer loop iteration, the queue contains exactly the nodes on one level, ordered from left to right.

The algorithm processes all nodes in that level.

The last processed node is therefore the rightmost node of that level.

That node is exactly the one visible from the right side.

The algorithm appends one such value for every level and processes levels from top to bottom.

Therefore, the returned list is exactly the binary tree’s right side view.

Complexity

Here, n is the number of nodes, and w is the maximum width of the tree.

Implementation

from collections import deque
from typing import Optional

# Definition for a binary tree node.
# 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: Optional[TreeNode]) -> list[int]:
        if root is None:
            return []

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

        while queue:
            level_size = len(queue)

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

                if i == level_size - 1:
                    ans.append(node.val)

                if node.left:
                    queue.append(node.left)

                if node.right:
                    queue.append(node.right)

        return ans

Code Explanation

This handles the empty tree:

if root is None:
    return []

The queue starts with the root:

queue = deque([root])

At each level, we freeze the current queue length:

level_size = len(queue)

This matters because new children are added to the queue while we process the current level.

The loop processes exactly the current level:

for i in range(level_size):

The last node of the level is detected by:

if i == level_size - 1:
    ans.append(node.val)

Then we add children for the next level:

if node.left:
    queue.append(node.left)

if node.right:
    queue.append(node.right)

Finally:

return ans

returns the visible nodes from top to bottom.

Alternative Implementation: DFS Right First

We can also solve this with depth-first search.

The idea is to visit the right child before the left child.

The first node we see at each depth is the rightmost node for that depth.

from typing import Optional

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

        def dfs(node: Optional[TreeNode], depth: int) -> None:
            if node is None:
                return

            if depth == len(ans):
                ans.append(node.val)

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

        dfs(root, 0)
        return ans

This version uses recursion.

Its space complexity is O(h), where h is the height of the tree, excluding the output list.

Testing

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def run_tests():
    s = Solution()

    root = TreeNode(
        1,
        TreeNode(2, None, TreeNode(5)),
        TreeNode(3, None, TreeNode(4)),
    )
    assert s.rightSideView(root) == [1, 3, 4]

    root = TreeNode(1, None, TreeNode(3))
    assert s.rightSideView(root) == [1, 3]

    root = None
    assert s.rightSideView(root) == []

    root = TreeNode(1, TreeNode(2), None)
    assert s.rightSideView(root) == [1, 2]

    root = TreeNode(
        1,
        TreeNode(2, TreeNode(4), None),
        TreeNode(3),
    )
    assert s.rightSideView(root) == [1, 3, 4]

    print("all tests passed")

run_tests()

Test meaning: