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 to Solve:

1. Level Order Traversal (BFS): We'll use Breadth-First Search (BFS) to traverse the tree level by level. This ensures we visit nodes from left to right within each level.

2. Store Rightmost Node: For each level, we only care about the rightmost node's value. We'll keep track of this using a variable.

3. Collect Results: As we process each level, we'll add the rightmost node's value to our result list.

Explanation:

The key idea is that the rightmost node on each level is the last node visited in that level during a BFS traversal. We can use a queue to implement BFS. At each level, we process all nodes and only retain the value of the last node processed.

Code (Java):

import java.util.*;

public class BinaryTreeRightSideView {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            int rightmostValue = -1; // Initialize with an impossible value

            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                rightmostValue = node.val; // Update rightmostValue in each iteration

                if (node.right != null) {
                    queue.offer(node.right);
                }
                if (node.left != null) {
                    queue.offer(node.left);
                }
            }
            result.add(rightmostValue);
        }
        return result;
    }


    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}

Complexity Analysis:

• Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node exactly once.
• Space Complexity: O(W), where W is the maximum width of the tree. In the worst-case scenario (a complete binary tree), W can be equal to N, making the space complexity O(N). This is due to the queue used in BFS, which can store up to W nodes at a time. In the best case (a skewed tree) W is O(1).