We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Binary Tree Right Side View

Number: 199

Difficulty: Medium

Paid? No

Companies: Meta, Amazon, Yandex, Oracle, Google, Uber, ServiceNow, Microsoft, Bloomberg, Walmart Labs, TikTok, Adobe, Wix

Problem Description

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

Key Insights

  • The problem is essentially about capturing the last node at each level (or the rightmost node) in a binary tree.
  • A Breadth-First Search (BFS) approach naturally works by processing nodes level by level.
  • Alternatively, Depth-First Search (DFS) can be adapted by prioritizing the right subtree first, ensuring that the first node encountered at each depth is the visible one.
  • The number of nodes is capped at 100, so both approaches are efficient.

Space and Time Complexity

Time Complexity: O(n) - we visit every node in the tree.
Space Complexity: O(n) - in the worst case, the queue (or call stack for DFS) may hold all nodes of the tree.

Solution

We can solve this problem using BFS (level-order traversal). The idea is to traverse the tree level by level using a queue. For each level, the last element added to the level represents the rightmost view from that level. We then append that element’s value to our result list.

Alternatively, a DFS approach can be used where we visit the right subtree first. By keeping track of the current depth and checking if it’s the first time we’ve encountered this depth, we can add the first node visited at that depth (which will be the rightmost one) to the result.

In both approaches, appropriate data structures (a queue for BFS or recursion with a list for DFS) are used to store nodes and track the traversal state.

Code Solutions

# Python solution using BFS
from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val              # Node value
        self.left = left            # Left child
        self.right = right          # Right child

def rightSideView(root):
    # If the tree is empty, return an empty list
    if not root:
        return []
    
    right_view = []               # List to store right side view
    queue = deque([root])         # Initialize queue with the root node
    
    while queue:
        level_size = len(queue)   # Number of nodes in current level
        for i in range(level_size):
            node = queue.popleft()  # Get the front node from the queue
            # if it's the last node in the current level, add it.
            if i == level_size - 1:
                right_view.append(node.val)
            # add left child if exists
            if node.left:
                queue.append(node.left)
            # add right child if exists
            if node.right:
                queue.append(node.right)
    
    return right_view
← Back to All Questions