Find Largest Value in Each Tree Row

medium tree bfs

Problem

Given the root of a binary tree, return the largest value in each row of the tree (zero-indexed).

Inputtree = [1, 3, 2, 5, 3, null, 9]

Output[1, 3, 9]

Row 0 max = 1, row 1 max = 3, row 2 max = 9.

tree (level-order, "null" for empty)

from collections import deque

def largest_values(root):
    if not root:
        return []
    q = deque([root])
    ans = []
    while q:
        sz = len(q)
        best = float("-inf")
        for _ in range(sz):
            n = q.popleft()
            if n.val > best:
                best = n.val
            if n.left:
                q.append(n.left)
            if n.right:
                q.append(n.right)
        ans.append(best)
    return ans

function largestValues(root) {
  if (!root) return [];
  const ans = [];
  let level = [root];
  while (level.length) {
    let best = -Infinity;
    const next = [];
    for (const n of level) {
      if (n.val > best) best = n.val;
      if (n.left) next.push(n.left);
      if (n.right) next.push(n.right);
    }
    ans.push(best);
    level = next;
  }
  return ans;
}

class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if (root == null) return ans;
        Deque<TreeNode> q = new ArrayDeque<>();
        q.offer(root);
        while (!q.isEmpty()) {
            int sz = q.size();
            int best = Integer.MIN_VALUE;
            for (int i = 0; i < sz; i++) {
                TreeNode n = q.poll();
                best = Math.max(best, n.val);
                if (n.left != null) q.offer(n.left);
                if (n.right != null) q.offer(n.right);
            }
            ans.add(best);
        }
        return ans;
    }
}

vector<int> largestValues(TreeNode* root) {
    vector<int> ans;
    if (!root) return ans;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int sz = q.size(), best = INT_MIN;
        for (int i = 0; i < sz; i++) {
            TreeNode* n = q.front(); q.pop();
            best = max(best, n->val);
            if (n->left) q.push(n->left);
            if (n->right) q.push(n->right);
        }
        ans.push_back(best);
    }
    return ans;
}

Explanation

We need the biggest value on each row of the tree. Since the answer is organized by level, a level-by-level BFS fits perfectly — handle one full row, record its max, then move to the next row.

The loop holds the current level in a list. For that level we start best at negative infinity and scan every node, keeping the largest val we see. Along the way we collect all the children into a next list for the following round.

After the whole row is scanned, we push best onto ans and replace the level with next. When there are no more nodes, ans holds one max per level in top-to-bottom order.

Because each node is looked at exactly once, the whole thing runs in linear time, and we only ever store one level at a time.

Example: [1, 3, 2, 5, 3, null, 9]. Row 0 is [1] with max 1, row 1 is [3, 2] with max 3, and row 2 is [5, 3, 9] with max 9, giving [1, 3, 9].

Time: O(n) Space: O(w)