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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Binary Tree Right Side View

Difficulty: Medium

Problem Description

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.

Key Insights

  • The rightmost node at each level of the binary tree is visible when viewed from the right side.
  • A level-order traversal (BFS) or a depth-first traversal (DFS) can be used to explore the tree.
  • Using a queue (for BFS) or a stack (for DFS) helps to keep track of the nodes at each level and ensure we capture only the rightmost node.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the tree, as we need to visit each node once. Space Complexity: O(h), where h is the height of the tree, due to the space used by the recursion stack (in the case of DFS) or the queue (in the case of BFS).

Solution

To solve this problem, we can use either a Depth-First Search (DFS) or a Breadth-First Search (BFS) approach.

  1. Data Structures:

    • For DFS, we can use a stack to traverse the tree.
    • For BFS, we will use a queue to explore each level of the tree.

  2. Algorithm:

    • Perform a level order traversal of the binary tree.
    • At each level, the last node processed will be the rightmost node.
    • Capture the values of these rightmost nodes and return them as the output.

Code Solutions

from collections import deque

def rightSideView(root):
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level_length = len(queue)
        for i in range(level_length):
            node = queue.popleft()
            # If it's the last node of this level, add to result
            if i == level_length - 1:
                result.append(node.val)
            # Add left and right children to the queue
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    
    return result
← Back to All Questions