Binary Tree Right Side View
Given the root of a binary tree, return the rightmost node value in the nth level, where the root is at level 1 and the rightmost node is at level 1.
Constraints:
- The number of nodes in the tree is in the range [1, 100].
- 1 <= Node.val <= 100
Examples:
Input: [1,2,3,null,5,null,4]
Output: [1,3,4]
Explanation: The rightmost node values in each level are 1, 3, and 4.
Solutions
Breadth-First Search (BFS)
Time: O(N)Space: O(N)
We use a queue to perform a level-order traversal of the binary tree. In each level, we add the rightmost node's value to the result list.
var rightSideView = function (root) {
const result = [];
if (!root) return result;
const queue = [root];
while (queue.length) {
const levelSize = queue.length;
for (let i = 0; i < levelSize; i++) {
const node = queue.shift();
if (i === levelSize - 1) result.push(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
}
return result;
};
Follow-up:
Can you solve this problem using a recursive approach?
