199. Binary Tree Right Side View - Explanation

Description

You are given the root of a binary tree. Return only the values of the nodes that are visible from the right side of the tree, ordered from top to bottom.

Example 1:

Input: root = [1,2,3]

Output: [1,3]

Example 2:

Input: root = [1,2,3,4,5,6,7]

Output: [1,3,7]

Constraints:

0 <= number of nodes in the tree <= 100
-100 <= Node.val <= 100

Recommended Time & Space Complexity

You should aim for a solution with O(n) time and O(n) space, where n is the number of nodes in the given tree.

Hint 1

In the right-side view of a tree, can you identify the nodes that are visible? Maybe you could traverse the tree level by level and determine which nodes are visible from the right side.

Hint 2

The nodes visible in the right-side view are the last nodes at each level of the tree. Can you think of an algorithm to identify these nodes? Maybe an algorithm that can traverse the tree level by level.

Hint 3

We can use the Breadth First Search (BFS) algorithm to traverse the tree level by level. Once we completely visit a level, we take the last node of that level and add it to the result array. After processing all levels, we return the result.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Depth First Search

Intuition

To see the right side of a tree, at each depth we only care about the first node we encounter when looking from the right.

If we perform DFS by visiting:

Right child first, then
Left child

…then the first node we reach at every depth is the visible right-side node.

We store that node the moment we first reach that depth.

Algorithm

Create an empty list res to store the right-side values.
Define a dfs function that takes a node and its depth.
In the dfs:
- If the node is null → return.
- If depth == len(res) → this is the first node at this depth → append its value.
- Recursively visit the right child first.
- Then recursively visit the left child.
Start dfs from the root at depth 0.
Return res.

# 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]:
        res = []

        def dfs(node, depth):
            if not node:
                return None
            if depth == len(res):
                res.append(node.val)

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

        dfs(root, 0)
        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

2. Breadth First Search

Intuition

In BFS we explore the tree level by level.
If we look at each level from left to right, the last node we encounter at that level is the one visible from the right side.

So for every level:

Traverse all nodes.
Remember the rightmost node.
Add it to the answer.

Algorithm

If the tree is empty → return an empty list.
Initialize a queue with the root.
While the queue is not empty:
- Determine how many nodes are in the current level (level_size).
- For each node in the level:
  - Pop it from the queue.
  - Update rightmost_node to this node.
  - Push its left child, then right child (if they exist).
- After finishing the level, append rightmost_node's value to the result.
Return the result list.

# 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]:
        res = []
        q = deque([root])

        while q:
            rightSide = None
            qLen = len(q)

            for i in range(qLen):
                node = q.popleft()
                if node:
                    rightSide = node
                    q.append(node.left)
                    q.append(node.right)
            if rightSide:
                res.append(rightSide.val)
        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

Common Pitfalls

Only Traversing Right Children

The rightmost visible node at each level is not always in the right subtree. When the right subtree is shorter than the left, deeper left nodes become visible from the right.

# Wrong: misses left nodes visible at deeper levels
def dfs(node):
    if node:
        res.append(node.val)
        dfs(node.right)  # must also check node.left

Using DFS With Left-First Traversal Without Adjustment

In DFS, if you visit left children before right children, you must update (not just set) the result for each depth. Otherwise, only left-side nodes are captured.

# Wrong with left-first DFS: captures left side, not right
if depth == len(res):
    res.append(node.val)  # never updates if left visited first

Forgetting to Track Level Size in BFS

In BFS, you must process all nodes at the current level before moving to the next. Without tracking the level size, you cannot determine which node is rightmost at each level.