Binary Tree Right Side View medium

Problem Statement

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.

Example 1:

Input: root = [1,2,3,null,5,null,4] Output: [1,3,4]

Example 2:

Input: root = [1,null,3] Output: [1,3]

Steps

1. Initialization: Create a list result to store the rightmost nodes' values, and a queue queue to perform a Breadth-First Search (BFS). Add the root node to the queue.

2. BFS Traversal: While the queue is not empty:

   • Get the size level_size of the queue. This represents the number of nodes at the current level.
   • Iterate level_size times:
     • Dequeue a node from the queue.
     • If it's the last node processed at this level (i.e., the rightmost node), append its value to result.
     • Enqueue the node's left and right children (if they exist).

3. Return: Return the result list.

Explanation

This problem is best solved using Breadth-First Search (BFS). BFS explores the tree level by level. By keeping track of the size of each level, we can easily identify the rightmost node at each level. The rightmost node at each level is the last node processed for that level in a BFS traversal.

Code

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def rightSideView(root):
    if not root:
        return []

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

    while queue:
        level_size = len(queue)
        for i in range(level_size):
            node = queue.popleft()
            if i == level_size - 1:  # Last node at the current level
                result.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    return result


#Example Usage
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.right = TreeNode(5)
root.right.right = TreeNode(4)

print(rightSideView(root)) # Output: [1, 3, 4]

root2 = TreeNode(1)
root2.right = TreeNode(3)
print(rightSideView(root2)) #Output: [1,3]

Complexity

• Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node once during the BFS traversal.
• Space Complexity: O(W), where W is the maximum width of the tree. In the worst case (a complete binary tree), W can be proportional to N. The space is mainly used by the queue to store nodes at each level.