⚡Flashcard Drill➔
NeetCode #425LC-199MediumTreesNC 150NC 250
← Back to All Problems

#425 · #199 · Binary Tree Right Side View(二叉树的右视图)

📌 Problem Statement & Constraints

Given the root of a binary tree, imagine standing on the right side of it and return the values of the nodes visible from top to bottom. Constraints: the number of nodes is in [0, 100].

💡 Core Algorithmic Approaches

  1. This is a level-order traversal where only the last node of each level is recorded.
  2. BFS with a frozen level size makes this trivial: the node at index n - 1 is the rightmost.
  3. A DFS that visits the right child first and records the first node seen at each new depth is an equally valid approach.
  4. Both are O(n).

💻 Benchmark Python3 Implementation

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        from collections import deque
        if not root:
            return []
        res = []
        q = deque([root])
        while q:
            n = len(q)
            for i in range(n):
                node = q.popleft()
                if i == n - 1:             # the rightmost node of this level
                    res.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
        return res


# DFS variant: right child first, record the first node at each new depth
class Solution2:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        res = []

        def dfs(node: Optional[TreeNode], depth: int) -> None:
            if not node:
                return
            if depth == len(res):          # first node seen at this depth
                res.append(node.val)
            dfs(node.right, depth + 1)     # right first -> rightmost wins
            dfs(node.left, depth + 1)

        dfs(root, 0)
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): every node is visited once.
💾 Space Complexity
O(w) for the BFS queue, or O(h) for the DFS recursion stack.

⚠️ Interview Pitfalls & Follow-ups

  • Taking the first node of each level in BFS: that is the left view; the right view needs the last node.
  • Visiting the left child first in the DFS variant: the leftmost node would be recorded instead.
  • Using depth == len(res) as the condition: this works precisely because the right child is explored first.
  • Forgetting the empty-tree case: an empty tree has an empty view.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Trees Problems