algoadvance

Problem Statement

You are given the root of a binary tree. Imagine yourself standing on the right side of it; you should return the values of the nodes you can see ordered from top to bottom.

Clarifying Questions

  1. What should be returned if the tree is empty?
    • Return an empty list.
  2. Can nodes have duplicate values?
    • Yes, nodes can have duplicate values.
  3. What is the expected output for a right-skewed tree or a left-skewed tree?
    • For a right-skewed tree, all nodes will be visible. For a left-skewed tree, only one node per level will be visible, as no nodes obscure the view from the right side.

Strategy

The strategy to solve this problem can be broken down into the following steps:

  1. Level-order Traversal (Breadth-First Search):
    • Use a queue to perform a level-order traversal of the tree.
    • For each level of the tree, keep track of the last node’s value, since that will be the one visible from the right side.

Code

from collections import deque

# 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

def rightSideView(root: TreeNode) -> list[int]:
    if not root:
        return []

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

    while queue:
        level_length = len(queue)
        for i in range(level_length):
            node = queue.popleft()
            if i == level_length - 1:
                # the rightmost element of this level
                right_view.append(node.val)
                
            if node.left:
                queue.append(node.left)
                
            if node.right:
                queue.append(node.right)

    return right_view

Time Complexity

The time complexity of this approach is O(N), where (N) is the number of nodes in the binary tree. This is because we’re visiting each node exactly once during the traversal.

The space complexity is also O(N) in the worst case. This is due to the queue used for the breadth-first search, which in the worst case can store up to half the number of nodes at the last level of a complete binary tree.

Try our interview co-pilot at AlgoAdvance.com