Binary Tree Right Side View

medium tree bfs

Problem

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.

Inputlevel-order: [4, 2, 7, _, 5, _, 9]

Output[4, 7, 9]

Level 0: 4. Level 1: 7 (rightmost). Level 2: 9 (rightmost).

level-order ('_' for null)

def right_side_view(root):
    if root is None: return []
    out = []
    level = [root]
    while level:
        out.append(level[-1].val)
        nxt = []
        for n in level:
            if n.left: nxt.append(n.left)
            if n.right: nxt.append(n.right)
        level = nxt
    return out

function rightSideView(root) {
  if (!root) return [];
  const out = [];
  let level = [root];
  while (level.length) {
    out.push(level[level.length - 1].val);
    const next = [];
    for (const n of level) {
      if (n.left) next.push(n.left);
      if (n.right) next.push(n.right);
    }
    level = next;
  }
  return out;
}

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        if (root == null) return new ArrayList<>();
        List<Integer> out = new ArrayList<>();
        List<TreeNode> level = new ArrayList<>(); level.add(root);
        while (!level.isEmpty()) {
            out.add(level.get(level.size() - 1).val);
            List<TreeNode> next = new ArrayList<>();
            for (TreeNode n : level) {
                if (n.left != null) next.add(n.left);
                if (n.right != null) next.add(n.right);
            }
            level = next;
        }
        return out;
    }
}

vector<int> rightSideView(TreeNode* root) {
    if (!root) return {};
    vector<int> out;
    vector<TreeNode*> level = { root };
    while (!level.empty()) {
        out.push_back(level.back()->val);
        vector<TreeNode*> next;
        for (auto* n : level) {
            if (n->left) next.push_back(n->left);
            if (n->right) next.push_back(n->right);
        }
        level = next;
    }
    return out;
}

Explanation

Standing on the right, the only node you can see on each row is the rightmost one. So if we process the tree one level at a time, the answer is simply the last node of each level.

This is a level-by-level BFS. We keep a list level of all nodes on the current row. The visible value is level[-1] (the last element), which we add to out.

To advance, we build the next level by scanning the current nodes left to right and collecting their children in order: left then right. Keeping this order guarantees the last element of the next list really is the rightmost node of that row.

Example: tree [4, 2, 7, _, 5, _, 9]. Level 0 is [4] → see 4. Level 1 is [2, 7] → see 7. Level 2 is [5, 9] → see 9. Result is [4, 7, 9].

Each node is enqueued and read once, so the work is O(n) time, using space proportional to the widest level.

Time: O(n) Space: O(w) for the widest level