# 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 | Item | Meaning | |---|---| | Input | Root of a binary tree | | Output | List of visible node values | | Order | From top to bottom | | Visible node | The rightmost node at each level | Example function shape: ```python def rightSideView(root: Optional[TreeNode]) -> list[int]: ... ``` ## Examples Example 1: ```text root = [1,2,3,null,5,null,4] ``` Tree: ```text 1 / \ 2 3 \ \ 5 4 ``` From the right side: | Level | Visible node | |---|---:| | 0 | 1 | | 1 | 3 | | 2 | 4 | Output: ```python [1, 3, 4] ``` Example 2: ```text root = [1,null,3] ``` Tree: ```text 1 \ 3 ``` Output: ```python [1, 3] ``` Example 3: ```text root = [] ``` Output: ```python [] ``` ## 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: ```text level nodes = [2, 3] ``` The rightmost node is `3`. So while processing the level, when the index is: ```python 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 | Metric | Value | Why | |---|---|---| | Time | `O(n)` | Each node is visited once | | Space | `O(w)` | The queue stores at most one level of nodes | Here, `n` is the number of nodes, and `w` is the maximum width of the tree. ## Implementation ```python 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: ```python if root is None: return [] ``` The queue starts with the root: ```python queue = deque([root]) ``` At each level, we freeze the current queue length: ```python 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: ```python for i in range(level_size): ``` The last node of the level is detected by: ```python if i == level_size - 1: ans.append(node.val) ``` Then we add children for the next level: ```python if node.left: queue.append(node.left) if node.right: queue.append(node.right) ``` Finally: ```python 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. ```python 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 ```python 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: | Test | Why | |---|---| | `[1,2,3,null,5,null,4]` | Main right-side example | | `[1,null,3]` | Right-only tree | | `[]` | Empty tree | | Left-only tree | Left nodes are visible when no right node exists | | Mixed tree | Later level can be visible from a left subtree |