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.

Example 1:

Input: root = [1,2,3,null,5,null,4]

Output: [1,3,4]

Explanation:

Example 2:

Input: root = [1,2,3,4,null,null,null,5]

Output: [1,3,4,5]

Explanation:

Example 3:

Input: root = [1,null,3]

Output: [1,3]

Example 4:

Input: root = []

Output: []

Constraints:

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

Solution:

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var rightSideView = function(root) {
    if (!root) {
        return [];
    }

    const result = [];
    let queue = [root];

    while (queue.length) {
        const last = queue[queue.length - 1];
        result.push(last.val);

        const nextLevel = [];
        queue.forEach((n) => {
            if (n.left) {
                nextLevel.push(n.left);
            }
            if (n.right) {
                nextLevel.push(n.right);
            }
        });
        queue = nextLevel;
    }

    return result;
};

This solution uses a breadth-first search (BFS) approach to traverse the binary tree level by level and extract the rightmost node of each level, which forms the right side view of the tree. The idea is to maintain a queue of nodes at the current level, push all their children into a new queue for the next level, and always record the last node in the current level as the visible node from the right.

We first check if the root is null. If it is, the function immediately returns an empty array since there are no nodes to view. Otherwise, we initialize a result array to store the rightmost values and a queue array containing only the root node, representing the first level.

The main loop runs as long as there are nodes in the queue. For each iteration, we identify the last node in the queue, which is the rightmost node of the current level, and push its value into the result array. We then prepare a nextLevel array to store all children of nodes in the current queue. Using forEach, we go through each node in the current level and push its left and right children (if they exist) into nextLevel. After processing all nodes in the current level, we assign nextLevel to queue and repeat the process for the next level.

Finally, after the loop finishes, the result array contains the rightmost node of each level, which is returned as the output.

For example, consider the tree:

        1
       / \
      2   3
       \   \
        5   4

• The first level has [1]. The rightmost node is 1, so result = [1].
• The second level has [2, 3]. The rightmost node is 3, so result = [1, 3].
• The third level has [5, 4]. The rightmost node is 4, so result = [1, 3, 4].

Thus, the function correctly returns [1, 3, 4] as the right side view.

This approach ensures that all levels are processed, and only the visible nodes from the right side are captured. The time complexity is O(n) because each node is visited exactly once, and the space complexity is O(w), where w is the maximum width of the tree, due to storing nodes at each level in the queue.