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. Level Order Traversal (BFS): We'll use Breadth-First Search (BFS) to traverse the tree level by level. This ensures we process nodes from top to bottom.

2. Keep Track of Rightmost Node: For each level, we only care about the rightmost node's value. We'll maintain a variable to store this value for each level.

3. Store Results: We'll collect the rightmost node's value from each level into a result array.

4. Return Result: After processing all levels, return the result array.

Explanation

The algorithm uses a queue for BFS. In each level, we iterate through all nodes in that level. The last node processed in a level is the rightmost node, and its value is added to the result array. The queue stores nodes to be visited, and we use a levelSize variable to control the number of nodes processed at each level, making it efficient for handling levels with varying numbers of nodes.

Code

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val===undefined ? 0 : val)
        this.left = (left===undefined ? null : left)
        this.right = (right===undefined ? null : right)
    }
}

function rightSideView(root: TreeNode | null): number[] {
    if (!root) return [];

    const result: number[] = [];
    const queue: TreeNode[] = [root];

    while (queue.length > 0) {
        const levelSize = queue.length;
        let rightmostNodeValue = 0; // Initialize to avoid potential undefined issues

        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift()!; // guaranteed to exist because queue.length > 0
            rightmostNodeValue = node.val; // update rightmost node for the current level

            if (node.left) {
                queue.push(node.left);
            }
            if (node.right) {
                queue.push(node.right);
            }
        }
        result.push(rightmostNodeValue);
    }

    return result;
}

Complexity

• Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node once.
• 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 (the number of nodes), making space complexity O(N). In a balanced tree, W will be much smaller than N. The queue holds nodes at a given level.