Binary Tree Right Side View – LeetCode75 Python Solution Explained

The Binary Tree Right Side View problem (LeetCode75) is a popular binary tree challenge that requires you to determine what a binary tree looks like when viewed from the right side. It is a common coding interview question because it tests your ability to use level-order traversal (BFS) or depth-first traversal (DFS) efficiently.

In this blog, we’ll go through the problem statement, work through examples, provide a Python solution, break down the logic step by step, analyze time and space complexity, discuss edge cases and explore real-world applications of this pattern.

Problem Statement

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

Example 1

Input:

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

Output:

[1, 3, 4]

Explanation:

• From the right side:
  • Level 1 → node 1 is visible
  • Level 2 → node 3 is visible
  • Level 3 → node 4 is visible

Example 2

Input:

root = [1,null,3]

Output:

[1, 3]

Example 3

Input:

root = []

Output:

[]

Complete Python Solution

from collections import deque
from typing import Optional, 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]:
        if not root:
            return []
        
        result = []
        queue = deque([root])

        while queue:
            level_size = len(queue)

            for i in range(level_size):
                node = queue.popleft()

                # Add the last node in the current level
                if i == level_size - 1:
                    result.append(node.val)
                
                # Push children into queue
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

        return result

Step-by-Step Solution Approach

We can solve this problem using BFS (level-order traversal):

Step 1: Handle the Base Case

If the tree is empty, return an empty list.

if not root:
    return []

Step 2: Initialize BFS Queue

We use a queue to perform level-order traversal. Each level will be processed one by one.

from collections import deque

queue = deque([root])
result = []

Step 3: Traverse Each Level

For every level, we track how many nodes are in it (level_size).

while queue:
    level_size = len(queue)

Step 4: Process Nodes in the Level

For each node in the level:

• Pop from the queue.
• If it’s the last node in that level, add it to the result (this represents the rightmost visible node).

for i in range(level_size):
    node = queue.popleft()
    if i == level_size - 1:   # last node at this level
        result.append(node.val)

Step 5: Push Child Nodes

Continue traversal by pushing the left and right children into the queue.

    if node.left:
        queue.append(node.left)
    if node.right:
        queue.append(node.right)

Time and Space Complexity

• Time Complexity: O(n) – Every node is visited once.
• Space Complexity: O(n) – At most, the queue will store all nodes of the last level in the tree.

Edge Cases

1. Empty tree → Return [].
2. Single node tree → Only the root is visible.
3. Tree skewed to the left → Only leftmost nodes are seen as right view.
4. Tree skewed to the right → All nodes are visible.

Real-World Applications

The right side view concept is similar to real-world situations where only the most prominent elements of a structure are visible from one perspective.

• Computer Graphics: Determining visible objects in rendering engines.
• Architecture Visualization: Viewing structural layers from a single direction.
• Hierarchical Data Visualization: Extracting the most “prominent” or rightmost entries in a hierarchy.
• Networking (Tree-based Routing): Determining the most direct visible path in hierarchical routing structures.

Conclusion

The Binary Tree Right Side View problem is a great example of applying BFS traversal effectively. By processing each level and capturing only the last node, we can determine what the binary tree looks like from the right side.

This pattern is highly valuable in interview preparation as it combines queue usage, tree traversal and edge-case handling. Beyond interviews, it has real-world applications in graphics, data visualization and tree-based modeling systems.

Related Reads

• Leaf-Similar Trees – LeetCode75 Python Solution Explained
• Lowest Common Ancestor of a Binary Tree – LeetCode75 Python Solution Explained
• Longest ZigZag Path in a Binary Tree – LeetCode75 Python Solution Explained
• Path Sum III – LeetCode75 Python Solution Explained
• Count Good Nodes in a Binary Tree – LeetCode75 Python Solution Explained

References

1. LeetCode – Binary Tree Right Side View
2. GeeksforGeeks – Right View of Binary Tree
3. Programiz – Binary Tree Data Structure
4. InterviewBit – Binary Tree Problems
5. TutorialsPoint – Binary Tree Concepts