Binary Tree Right Side View | Leetcode 199

Welcome to our multi-approach guide on Binary Tree Right Side View (Leetcode 199). This problem is an outstanding test of your ability to manipulate structural tree traversals. We aren't just traversing the tree; we want the exact structural array of nodes visible natively when looking horizontally from the absolute right perimeter!

Problem Statement

Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Example:

       1      <-- see 1
     /   \
    2     3   <-- see 3
     \     \
      5     4 <-- see 4

Output: [1, 3, 4]

Approach 1: Breadth-First-Search (BFS) Level Order O(N)

If we want the absolute right-most mapped structural boundary of the tree, the most intuitive native way to solve this is to simply analyze the tree layer by layer horizontally. If we isolate exactly one total horizontal level... the node that we "see" from the right side is mathematically identically strictly the last node existing in that horizontal array row!

We can use a Queue to execute a classic Level-Order BFS traversal.

1. Push the root to the internal queue.
2. For each dynamically sized level layer, pop every single node dynamically identically horizontally.
3. Keep overwriting a right_most_val variable iteratively as you sweep from left to right across that explicit layer!
4. When the layer finishes structurally cleanly, the right_most_val holds the final node! Append it to our master list.

from collections import deque

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        if not root: return res
        
        q = deque([root])
        
        while q:
            right_most = None
            q_len = len(q)
            
            # Sweep identically horizontally across this isolated depth layer
            for i in range(q_len):
                node = q.popleft()
                if node:
                    # Dynamically overwrite! The absolutely final evaluation will organically be the rightest node.
                    right_most = node
                    
                    if node.left: q.append(node.left)
                    if node.right: q.append(node.right)
                    
            if right_most:
                res.append(right_most.val)
                
        return res

Complexity Analysis

Approach 2: Depth-First-Search (DFS) Right-First Traversal

Can we avoid the massive horizontal Queue memory footprint allocating completely dynamically array sweeps? Yes, using an incredibly clever variation of recursive Depth-First Search.

Instead of a standard Left, Right sequence, we intentionally reverse it to Right, Left! Because we systematically evaluate the absolute structurally rightmost branches of the tree first mathematically... If we pass a depth integer tracker natively into our recursion block, the absolute first node we organically organically stumble upon for any undiscovered depth value IS definitively the absolute rightest node structurally!

We simply check: If Depth == len(Result Array). If this cleanly hits identically true natively... this is mathematically the first time we've historically broken this horizontal bound! We append our native node structure directly, and rely on the internal cache length structurally blocking all inferior identical left-branch depth calls from appending.

graph TD
    A["Depth 0 (Root 1)"] -->|"Right-First Search"| B["Depth 1 (Node 3)"]
    B --> C["Depth 2 (Node 4)"]
    
    A -.->|"Subsequent DFS Left"| D["Depth 1 (Node 2)"]
    D -.-> E["Depth 2 (Node 5)"]
    
    style A fill:#4CAF50,stroke:#fff,stroke-width:2px,color:#fff
    style B fill:#4CAF50,stroke:#fff,stroke-width:2px,color:#fff
    style C fill:#4CAF50,stroke:#fff,stroke-width:2px,color:#fff

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        
        def dfs(node, depth):
            if not node: return
            
            # Since we evaluate completely Right-First natively computationally,
            # this condition guarantees we only map the explicitly rightmost edge!
            if depth == len(res):
                res.append(node.val)
                
            # Right-First Priority execution!
            dfs(node.right, depth + 1)
            dfs(node.left, depth + 1)
            
        dfs(root, 0)
        return res

Complexity Analysis

Try it yourself!

Try this problem on LeetCode (199)