Leetcode 199. Binary Tree Right Side View

199. Binary Tree Right Side View

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.

Approach 1:


class Solution {
    public List rightSideView(TreeNode root) {
        List res = new ArrayList(); // to store ans
        helper(root, res, 0); // here 0 is level initially
        return res;
    }

    public static void helper(TreeNode root, List res, int level) {
        if (root == null)
            return;
        // if ds size == level means found node for first time, So add node to res
        if (level == res.size()) {
            res.add(root.val);
        }
        // call for its right child and with level increased to 1 as your'e moving to
        // next level
        helper(root.right, res, level + 1);
        // call for its left child and with level increased to 1 as your'e moving to
        // next level
        helper(root.left, res, level + 1);
    }
}

Time Complexity: O(n) and Space Complexity: O(n)

Introduction

The "Binary Tree Right Side View" problem is a common algorithmic challenge that involves finding the rightmost nodes visible from the right side of a binary tree. Given a binary tree, your task is to return a list of nodes that would be visible if you were to look at the tree from the right side.

This problem tests your understanding of tree traversal techniques, such as breadth-first search (BFS) or depth-first search (DFS). The idea is to ensure you can capture the rightmost node of each level in the tree.

Problem Statement

Given a binary tree, you are to return the values of the nodes that are visible from the right side. The right side view of a binary tree is the set of nodes that would be visible if you could view the tree from the right.

The binary tree is represented by the following structure:

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

The tree nodes are represented by instances of the TreeNode class.

Approach

The key to solving the Binary Tree Right Side View problem is to use a level-order traversal (BFS). The general idea is:

BFS Traversal: We traverse the tree level by level, starting from the root. At each level, we capture the rightmost node.
Track Rightmost Node: In each level, the last node processed (i.e., the last node enqueued in BFS) is the rightmost node. We add this node's value to the result list.
Queue Management: Use a queue to manage the nodes for BFS, ensuring that we process all nodes at each level before moving to the next level.

Algorithm

The algorithm can be described in the following steps:

Initialize a queue to perform BFS. Start by enqueuing the root node.
At each level, dequeue all the nodes and process them. For each level, capture the value of the last node processed (rightmost node).
If the node has a left child, enqueue it. Similarly, enqueue the right child if it exists.
Continue until all levels are processed.
Return the list of rightmost nodes.

Example

Let's consider an example of a binary tree:

The right side view of this tree is: [1, 3, 4]

- The rightmost node at the first level is 1. - The rightmost node at the second level is 3. - The rightmost node at the third level is 4.

Code Implementation

Below is a Python implementation of the Binary Tree Right Side View algorithm using BFS:

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_length = len(queue)
        # Iterate through all nodes at the current level
        for i in range(level_length):
            node = queue.popleft()
            # The rightmost node of the level will be added to the result
            if i == level_length - 1:
                result.append(node.val)
            # Add children to the queue for the next level
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    
    return result

In this code: - We use a queue to traverse the tree level by level. - For each level, we add the rightmost node to the result list. - At the end of the traversal, the result list contains the right side view of the binary tree.

Time Complexity

The time complexity of this algorithm is O(n), where n is the number of nodes in the tree. This is because we visit each node exactly once during the BFS traversal.

The space complexity is also O(n), since we use a queue to store the nodes at each level of the tree. In the worst case, the queue will store all the nodes at the bottom level, which can be up to n/2 nodes.

Conclusion

The "Binary Tree Right Side View" problem is a great exercise to practice tree traversal using BFS. By capturing the last node at each level, you can easily find the rightmost nodes of the binary tree. This problem helps improve your skills in handling tree structures and using queues for level-order traversal.