30% off Lifetime Premium Access expires December 2nd!

30% off Lifetime Premium Access expires Dec 2nd!

Your Dashboard

Interview Coaching

Mock Interviews

1:1 Mentorship

Salary Negotiation

Practice

Learn

System Design

ML System Design

Code

Behavioral

Salary Negotiation

Interview Guides

Blog

Community

Interview Questions

Interview Experiences

Peer System Design Library

Ask The Community

Discord

Refer a Friend

Pricing

Become a Coach

⌘K

Pricing Become a Coach

⌘K

Get Premium

Leetcode 199. Binary Tree Right Side View

Return the values visible when viewing a binary tree from its right side — i.e., the rightmost node at each depth, ordered top to bottom. This requires traversing the tree by level (or right-first DFS) and selecting one node per level.

Asked at:

Meta

DESCRIPTION

Given the root of a binary tree, return the rightmost node at each level of the tree.
The output should be a list containing only the values of those nodes.

Input:


root = [3,9,20,null,null,15,7]

Output:


[3,20,7]

Explanation: The rightmost nodes at each level are 3 (level 0), 20 (level 1), and 7 (level 2).

Constraints:

The number of nodes in the tree is in the range [0, 100]
Node values are in the range [-100, 100]

Note: The rightmost node is the last node encountered when traversing each level from left to right

If a level has only one node, that node is considered the rightmost

Understanding the Problem

This problem is asking us to imagine looking at a binary tree from the right side - what nodes would be visible? At each horizontal level of the tree, only the rightmost node would be visible from this perspective.

We need to identify these rightmost nodes level by level, starting from the root (level 0) and going down to the deepest level. The challenge is efficiently determining which node is the rightmost at each level without having to examine every possible node.

The key insight is that 'rightmost' means the last node we encounter when traversing each level from left to right. This naturally suggests a level-by-level traversal approach.

Brute Force Approach

The most straightforward approach would be to perform a complete level-order traversal of the entire tree, storing all nodes at each level in separate lists or arrays.

We would use BFS to traverse the tree level by level, collecting every single node at each depth. For each level, we'd maintain a list of all node values encountered during that level's traversal.

Once we've collected all nodes for a particular level, we'd simply take the last element from that level's list (since we traverse left to right, the last element is the rightmost). We'd repeat this process for every level until we've processed the entire tree.

This approach requires storing all nodes at each level temporarily, even though we only need the rightmost one, making it inefficient in terms of space usage.


from collections import deque

def rightSideView(root):
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level_size = len(queue)
        level_nodes = []  # Store ALL nodes at this level
        
        # Process all nodes at current level
        for i in range(level_size):
            node = queue.popleft()
            level_nodes.append(node.val)  # Store every node value
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        # Take the rightmost (last) node from this level
        rightmost_value = level_nodes[-1]
        result.append(rightmost_value)
    
    return result

Start binary tree right side view - brute force approach

0 / 34

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n) Due to checking all possible combinations

Space Complexity: O(n) Additional space for tracking

Building Intuition

The breakthrough insight is that we don't need to store or examine all nodes at a level - we just need to process them in order and remember the last one we see at each level.

By tracking the queue size at the start of each level, we know exactly how many nodes belong to the current level, allowing us to process them completely before moving to the next level.

After seeing the brute force limitations of storing entire levels, level-order traversal with BFS becomes the perfect approach because it processes nodes level by level in the exact order we need.

BFS using a queue naturally groups nodes by their depth level. When we process all nodes at level N, we automatically enqueue all nodes for level N+1. This level-by-level processing is exactly what we need to identify the rightmost node at each level.

The queue's FIFO property ensures we process nodes from left to right within each level, making the last node we process at each level the rightmost node by definition.

Common Mistakes

Trying to use simple DFS without depth tracking, which doesn't guarantee processing nodes level by level

Storing all nodes at each level instead of just tracking the rightmost one

Confusing 'rightmost' with 'right child' - the rightmost node might be a left child if the right subtree is shorter

Not handling the edge case of an empty tree

Forgetting that a single node at a level is considered the rightmost node

Optimal Solution

Now that we understand why level-order traversal is perfect, here's how we implement it efficiently using BFS with a queue.

We'll use a queue to process nodes level by level, but instead of storing all nodes at each level, we'll track only the rightmost node as we traverse each level.

The key insight is to process each level completely before moving to the next. We determine the number of nodes at the current level (queue size), then process exactly that many nodes. As we process each node in the current level, we keep updating our 'rightmost' variable - the last node we process in each level will naturally be the rightmost.

For each level: dequeue all nodes at that level, add their children to the queue for the next level, and capture the value of the last node processed. This gives us the rightmost node at each level without storing unnecessary intermediate results.


from collections import deque

def rightSideView(root):
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level_size = len(queue)
        rightmost = None
        
        # Process all nodes at current level
        for i in range(level_size):
            node = queue.popleft()
            rightmost = node.val
            
            # Add children for next level
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        # Add rightmost node value of current level
        result.append(rightmost)
    
    return result

Start binary tree right side view algorithm

0 / 21

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n) Single pass through the data

Space Complexity: O(w) Space for the data structure

What We've Learned

Level-order traversal (BFS) pattern: When you need to process a binary tree level by level, use a queue-based BFS approach - it naturally groups nodes by depth and processes them left-to-right, making it perfect for level-dependent problems like finding rightmost nodes.
Last element extraction technique: Instead of tracking rightmost nodes during traversal, process each level completely and simply take the last element from each level - this eliminates the need for complex right-first traversal logic and works regardless of tree structure.
Queue size snapshot optimization: Capture `queue.size()` at the start of each level and use it as your loop boundary - this ensures you process exactly one level at a time even as you add the next level's nodes to the queue during iteration.
Empty tree edge case: Always check for `root == null` before starting BFS traversal - attempting to add null to a queue or access properties of null nodes will cause runtime errors, and empty trees should return empty lists.
Level-based tree processing pattern: This BFS approach extends to any problem requiring level-wise analysis - finding level averages, detecting level-order patterns, or identifying nodes at specific depths all use the same queue-based level processing framework.

Test Your Understanding

Why is tree the right data structure for this problem?

tree provides the optimal access pattern

It's the only data structure that works

It's the easiest to implement

It uses the least memory

Select an answer to see the explanation

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Early November, 2025

Meta

Senior

Early October, 2025

Meta

Senior

Early October, 2025

Meta

Senior

Get Premium to View All 40+ Reports

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More

Leetcode 199. Binary Tree Right Side View

DESCRIPTION

Understanding the Problem

Brute Force Approach

Test Your Knowledge

Complexity Analysis

Building Intuition

Common Mistakes

Optimal Solution

Test Your Knowledge

Complexity Analysis

What We've Learned

Related Concepts and Problems to Practice

Test Your Understanding

Question Timeline

Comments

Questions

Learn

Links

Legal

Contact