Binary Tree Right Side View - Python Solution

1. Introduction

The "Binary Tree Right Side View" problem is a fascinating question that deals with viewing a binary tree from a unique perspective. It challenges one to visualize the tree from its right side and determine which nodes are visible in this view, traversing from top to bottom. This problem is an excellent way to understand breadth-first traversal and tree data structures.

Problem

Given the root of a binary tree, the task is to return the values of the nodes as seen from the right side of the tree, ordered from top to bottom.

2. Solution Steps

1. Use a breadth-first traversal to visit nodes level by level.

2. For each level of the tree, record the last node's value.

3. Implement a queue to keep track of nodes at each level.

4. Traverse each level, adding the children of each node to the queue for the next level.

5. After traversing each level, add the value of the last node to the result list.

3. Code Program

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

from collections import deque

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()
            # Add children for the next level
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
            # The last node in the current level will be visible from the right side
            if i == level_size - 1:
                result.append(node.val)

    return result

# Example Usage
root = TreeNode(1, TreeNode(2, None, TreeNode(5)), TreeNode(3, None, TreeNode(4)))
print(rightSideView(root))

Output:

[1, 3, 4]

Explanation:

1. Level Order Traversal: The algorithm performs a level order traversal using a queue.

2. Queue Management: Nodes at each level are added to and removed from the queue.

3. Last Node Recording: For each level, the value of the last node (rightmost node) is recorded.

4. Right View Construction: As the traversal proceeds level by level, the last node of each level forms the right view of the tree.

5. Result: The function returns a list of node values as seen from the right side of the binary tree.