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 queue to perform a Breadth-First Search (BFS) and a list to store the rightmost node values.
2. BFS Traversal: Enqueue the root node. While the queue is not empty:
   • Get the size of the queue (number of nodes at the current level).
   • Iterate through the nodes at the current level:
     • Dequeue a node.
     • Add the node's value to the rightmost node list only if it is the last node processed in the current level. This ensures we only get the rightmost node's value.
     • Enqueue the node's left and right children (if they exist).
3. Return Result: Return the list of rightmost node values.

Explanation

The key to this problem is using Breadth-First Search (BFS). BFS explores the tree level by level. By keeping track of the number of nodes at each level and only adding the last node's value processed at each level to the result list, we effectively capture the rightmost view. If a level has only one node, it will automatically be considered the rightmost node.

Code

using System.Collections.Generic;

public class Solution {
    public IList<int> RightSideView(TreeNode root) {
        IList<int> result = new List<int>();
        if (root == null) return result;

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

        while (queue.Count > 0) {
            int levelSize = queue.Count;
            int rightmostValue = 0; // Initialize to a default value.

            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.Dequeue();
                rightmostValue = node.val; // Update the rightmost value for this level

                if (node.left != null) {
                    queue.Enqueue(node.left);
                }
                if (node.right != null) {
                    queue.Enqueue(node.right);
                }
            }
            result.Add(rightmostValue);
        }

        return result;
    }

    public class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}

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 equal to N, but it will be significantly less than N for many tree shapes. The space is used by the queue to store nodes at each level.