LietCode
Binary Tree Right Side View (Medium)

Binary Tree Right Side View (Medium)

Abhi's photo
Abhi
·

3 min read

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]

Example 3:

Input: root = []
Output: []

1) Explain the problem

We need to determine which nodes of a binary tree are visible when viewed from the right side. We return the values of these nodes ordered from top to bottom.

2) Short easy to remember solution/approach

Use a level order traversal (BFS) to traverse the tree level by level. For each level, record the last node visited, as this node will be visible from the right side.

3) Solution in Javascript with code commenting

class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function rightSideView(root) {
    if (!root) return [];

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

    while (queue.length > 0) {
        const levelSize = queue.length;

        for (let i = 0; i < levelSize; i++) {
            const currentNode = queue.shift();

            // If it's the last node in the current level, add it to the result
            if (i === levelSize - 1) {
                result.push(currentNode.val);
            }

            // Add left and right children to the queue
            if (currentNode.left) queue.push(currentNode.left);
            if (currentNode.right) queue.push(currentNode.right);
        }
    }

    return result;
}

// Example usage:
let root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.right = new TreeNode(5);
root.right.right = new TreeNode(4);

console.log(rightSideView(root)); // Output: [1, 3, 4]

4) Explanation of the solution in an easy-to-understand way. Explain it like a 10-year-old.

Imagine you are looking at a building from the side. Each floor has a window on the rightmost side. As you look from the bottom to the top, you can only see the rightmost window of each floor. We need to find out which windows you can see from the side of the building.

5) Code explanation in pointers

  • Define a TreeNode class to represent each node in the tree.

  • Create a rightSideView function that:

    • Returns an empty array if the root is null.

    • Initializes an empty result array and a queue with the root node.

    • While the queue is not empty:

      • Determine the number of nodes at the current level (levelSize).

      • For each node at the current level:

        • Dequeue the node.

        • If it's the last node in the current level, add its value to the result array.

        • Enqueue its left and right children (if any).

    • Return the result array.

6) Complexities

  • Time Complexity: (O(n)) - Each node is visited once.

  • Space Complexity: (O(n)) - The queue holds at most the number of nodes in the last level, and the result array holds all visible node values.

TreeTrees