Binary Tree Right Side View - Leetcode Solution

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]

Example 3: Input: root = [] Output: []

Approach:

We can solve this problem using BFS (Breadth First Search) technique. The idea is to traverse the tree level by level and always keep the last node value of each level. So, the rightmost nodes will be visible from the right side of the binary tree.

Algorithm:

1. Create a list named result to store the right-side view of the binary tree.
2. Check if the given root is null or not.
3. If the root is null, then return the empty list result.
4. Initialize the queue with the root node.
5. Loop through the queue till it is empty: a. initialize the size equal to the length of the queue. b. Traverse each node level-wise from left to right. c. Check if the node is the last node for that level, then appent that node's value to the result list. d. If the left child of the node exists, then append it to the queue. e. If the right child of the node exists, then append it to the queue.
6. Finally return the result list, which contains the right-side view of the binary tree.

Code:

Here is the implementation of the algorithm in Python:

def rightSideView(root): result = [] if root is None: return result

queue = [root]
while queue:
    size = len(queue)
    for i in range(size):
        node = queue.pop(0)
        if i == size-1:
            result.append(node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
        
return result

Time Complexity:

The time complexity of the above algorithm is O(n), where n is the number of nodes in the binary tree. We traverse each node only once.

Space Complexity:

The space complexity of the above algorithm is O(n), where n is number of nodes in the binary tree. In the worst case, the queue can have all the nodes of the last level. So, the space complexity will be O(n).

This is the detailed solution of the Binary Tree Right Side View problem on Leetcode.

1