LeetCode 199: Binary Tree Right Side View Solution in Python Explained

Problem Statement

In LeetCode 199, you’re given the root of a binary tree defined by:

• TreeNode class: val (int), left (TreeNode), right (TreeNode).

Your task is to return a list of integers where each value is the rightmost node’s value at each level, from root to deepest level. This differs from dynamic programming like LeetCode 198: House Robber, focusing on tree traversal rather than optimization.

Constraints

• Number of nodes: 0 ≤ n ≤ 100.
• -100 ≤ Node.val ≤ 100.

Example

Let’s see some cases:

Copy codeInput: root = [1,2,3,null,5,null,4]
Tree:
    1
   / \
  2   3
   \   \
    5   4
Output: [1,3,4]
Explanation:
<ul>
<li>Level 0: 1 (rightmost = 1).</li>
<li>Level 1: 3 (rightmost = 3, 2 on left).</li>
<li>Level 2: 4 (rightmost = 4, 5 on left).</li>
</ul>

Copy codeInput: root = [1,null,3]
Tree:
    1
     \
      3
Output: [1,3]
Explanation:
<ul>
<li>Level 0: 1.</li>
<li>Level 1: 3.</li>
</ul>

Copy codeInput: root = []
Output: []
Explanation: Empty tree.

These examples show we’re collecting rightmost values per level.

Understanding the Problem

How do you solve LeetCode 199: Binary Tree Right Side View in Python? Take the tree [1,2,3,null,5,null,4]. We need [1,3,4], the rightmost nodes at each level:

• Level 0: 1.
• Level 1: 2 and 3, take 3 (rightmost).
• Level 2: 5 and 4, take 4 (rightmost).

A brute-force depth-first search (DFS) could collect all nodes per level, but we need only the rightmost, suggesting breadth-first search (BFS) or a smart DFS. This isn’t an SQL task like LeetCode 197: Rising Temperature; it’s about tree traversal. We’ll use: 1. Breadth-First Search with Level Tracking: O(n) time, O(w) space—our best solution (w = max width). 2. Depth-First Search with Preorder: O(n) time, O(h) space—an alternative (h = height).

Let’s dive into the best solution.

Best Solution: Breadth-First Search with Level Tracking Approach

Explanation

Breadth-First Search with Level Tracking finds the right side view by:

• Using a queue to process nodes level by level (BFS).
• For each level:
• Process all nodes, tracking size of the level.
• Take the last node’s value (rightmost).
• Append each level’s rightmost value to the result list.

This achieves O(n) time (visit each node once), O(w) space (queue holds max width), and clarity by leveraging BFS’s level-order traversal, making it intuitive and efficient.

For [1,2,3,null,5,null,4]:

• Level 0: [1] → 1.
• Level 1: [2,3] → 3.
• Level 2: [5,4] → 4.
• Result: [1,3,4].

Step-by-Step Example

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

Goal: Return [1,3,4].

• Step 1: Initialize.
• result = [], queue = deque([(root, 0)]) (node, level).
• Step 2: BFS loop.
• Level 0: queue = [(1, 0)].
• Size = 1, pop (1, 0) → val=1.
• Add left (2, 1), right (3, 1).
• Last node: 1 → result = [1].
• queue = [(2, 1), (3, 1)].
• Level 1: Size = 2.
• Pop (2, 1) → val=2, add (5, 2).
• Pop (3, 1) → val=3, add (4, 2).
• Last node: 3 → result = [1,3].
• queue = [(5, 2), (4, 2)].
• Level 2: Size = 2.
• Pop (5, 2) → val=5.
• Pop (4, 2) → val=4.
• Last node: 4 → result = [1,3,4].
• queue = [].
• Step 3: Finish.
• Queue empty, return [1,3,4].
• Finish: Return [1,3,4].

Example 2: root = [1,null,3]

Goal: Return [1,3].

• Step 1: queue = [(1, 0)], result = [].
• Step 2: BFS:
• Level 0: Size=1, pop (1, 0) → 1, add (3, 1), result = [1].
• Level 1: Size=1, pop (3, 1) → 3, result = [1,3].
• Finish: Return [1,3].

How the Code Works (Breadth-First Search with Level Tracking) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

Copy codefrom collections import deque

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

def rightSideView(root: TreeNode) -> list[int]:
    # Line 1: Handle empty tree
    if not root:
        # No nodes (e.g., [])
        return []

    # Line 2: Initialize result and queue
    result = []
    # List for rightmost values (e.g., [])
    queue = deque([(root, 0)])
    # Queue with (node, level) (e.g., [(1, 0)])

    # Line 3: BFS loop
    while queue:
        # Continue until queue empty (e.g., process levels)

        # Line 4: Process level
        level_size = len(queue)
        # Number of nodes in current level (e.g., 1)
        for i in range(level_size):
            # Iterate all nodes in level (e.g., 0 to 0)

            # Line 5: Dequeue node and level
            node, level = queue.popleft()
            # Current node and level (e.g., (1, 0))

            # Line 6: Add rightmost value
            if i == level_size - 1:
                # Last node in level (e.g., 1 at level 0)
                result.append(node.val)
                # Add to result (e.g., [1])

            # Line 7: Enqueue children
            if node.left:
                # Left child (e.g., (2, 1))
                queue.append((node.left, level + 1))
            if node.right:
                # Right child (e.g., (3, 1))
                queue.append((node.right, level + 1))

    # Line 8: Return right side view
    return result
    # e.g., [1, 3, 4]

This detailed breakdown clarifies how BFS with level tracking efficiently finds the right side view.

Alternative: Depth-First Search with Preorder Approach

Explanation

Depth-First Search with Preorder finds the right side view by:

• Using DFS with preorder traversal (root, right, left).
• Tracking level and updating result list when a new level is reached.
• Right-first ensures rightmost node is seen first per level.

It’s a practical alternative, O(n) time (visit each node), O(h) space (recursion stack, h = height), and intuitive for right-side preference, though less level-explicit than BFS.

For [1,2,3,null,5,null,4]:

• DFS: 1 (level 0), 3 (1), 4 (2), 2 (1, skipped), 5 (2, skipped).
• Result: [1,3,4].

Step-by-Step Example (Alternative)

For [1,2,3,null,5,null,4]:

• Step 1: result = [], DFS from root.
• Step 2: Preorder:
• (1, 0): New level 0 → [1].
• (3, 1): New level 1 → [1,3].
• (4, 2): New level 2 → [1,3,4].
• (2, 1): Level 1 exists, skip.
• (5, 2): Level 2 exists, skip.
• Finish: Return [1,3,4].

How the Code Works (DFS)

Copy codedef rightSideViewDFS(root: TreeNode) -> list[int]:
    result = []
    def dfs(node: TreeNode, level: int) -> None:
        if not node:
            return
        if level == len(result):
            result.append(node.val)
        dfs(node.right, level + 1)
        dfs(node.left, level + 1)
    dfs(root, 0)
    return result

Complexity

• Breadth-First Search with Level Tracking:
• Time: O(n) – visit each node.
• Space: O(w) – queue size (max width).
• Depth-First Search with Preorder:
• Time: O(n) – visit each node.
• Space: O(h) – recursion stack (height).

Efficiency Notes

Breadth-First Search with Level Tracking is the best solution with O(n) time and O(w) space, offering clarity and level-order intuition—Depth-First Search with Preorder matches time complexity but uses O(h) space, potentially less in skewed trees, though less explicit for level handling.

Key Insights

• BFS: Level-by-level, rightmost last.
• DFS: Right-first preorder.
• Rightmost: Key focus.

Additional Example

For [1,2,null,3]:

• Goal: [1,2,3].
• BFS: Level 0: 1, Level 1: 2, Level 2: 3.

Edge Cases

• Empty: [].
• Single Node: [val].
• Skewed Tree: Rightmost at each depth.

Both solutions handle these well.

Final Thoughts

LeetCode 199: Binary Tree Right Side View in Python is a classic tree traversal challenge. The Breadth-First Search with Level Tracking solution excels with its intuitive level-order approach, while Depth-First Search with Preorder offers a recursive alternative. Want more? Try LeetCode 102: Binary Tree Level Order Traversal for full levels or LeetCode 94: Binary Tree Inorder Traversal for inorder skills. Ready to practice? Solve LeetCode 199 on LeetCode with [1,2,3,null,5,null,4], aiming for [1,3,4]—test your skills now!