Leetcode - 199. Binary Tree Right Side View

🧠 Approach: Level Order Traversal (BFS)

We use Breadth-First Search (BFS) — traverse the tree level by level and at each level, capture the last node, which is visible from the right.

Steps:

1. Use a queue for level-order traversal.
2. At each level, keep track of the last node visited.
3. Add that node’s value to the result list.

---

✅ Code (JavaScript):

/**
 * 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 === null) return [];

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

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

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

      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }

    result.push(rightMost.val);
  }

  return result;
};

---

⏱️ Time & Space Complexity

Type	Complexity
Time	O(n) — Every node is visited exactly once
Space	O(n) — In worst case, queue holds one level of the tree (up to n/2 nodes)

---

📌 Example:

Input:

       1
      / \
     2   3
      \   \
       5   4

Output: [1, 3, 4]
(You see the rightmost node at each level.)

---