Right-Side View of a Tree

medium tree bfs

Problem

Standing on the right of a binary tree and looking inward, return the values of the nodes you can see, ordered from top to bottom. Run a level-order traversal and pick the last node seen on each level.

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;
}

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