Find Largest Value in Each Tree Row

Medium
1922.

Find Largest Value in Each Tree Row

Find Largest Value in Each Tree Row is a medium coding problem on depth-first search, breadth-first search and trees, asked in Amazon, Meta and LinkedIn interviews.

Given the root of a binary tree, return an array whose i-th element is the largest value in row i of the tree (row 0 holds the root, row 1 its children, and so on).

Example 1

Input
root = [1,3,2,5,3,null,9]
Output
[1,3,9]
Explanation
Row by row: {1}, {3, 2}, {5, 3, 9}. The largest of each is 1, 3 and 9.

Example 2

Input
root = [1,2,3]
Output
[1,3]
Explanation
The second row holds 2 and 3.

Example 3

Input
root = []
Output
[]
Explanation
An empty tree has no rows.

Constraints

  • The number of nodes in the tree is in the range [0, 10^4]
  • -2^31 <= Node.val <= 2^31 - 1
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * 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 largestValues = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find Largest Value in Each Tree Row — Problem & Solution

Find Largest Value in Each Tree Row solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Find Largest Value in Each Tree Row is a medium coding problem on depth-first search, breadth-first search and trees, asked in Amazon, Meta and LinkedIn interviews.

Problem statement

Given the root of a binary tree, return an array whose i-th element is the largest value in row i of the tree (row 0 holds the root, row 1 its children, and so on).

Example 1

Input: root = [1,3,2,5,3,null,9]
Output: [1,3,9]
Explanation: Row by row: {1}, {3, 2}, {5, 3, 9}. The largest of each is 1, 3 and 9.

Example 2

Input: root = [1,2,3]
Output: [1,3]
Explanation: The second row holds 2 and 3.

Example 3

Input: root = []
Output: []
Explanation: An empty tree has no rows.

Constraints

  • The number of nodes in the tree is in the range [0, 10^4]
  • -2^31 <= Node.val <= 2^31 - 1

Hints for Find Largest Value in Each Tree Row

  1. Hint 1

    You need to know which nodes share a row — a breadth-first walk hands them to you one row at a time.

  2. Hint 2

    Process the queue in batches: the queue's size at the start of a batch is exactly the number of nodes in that row.

  3. Hint 3

    Start each row's maximum from its first node rather than from a sentinel — the values reach the full 32-bit range.

How to solve Find Largest Value in Each Tree Row

Level-order traversal groups the nodes by row. Scanning each row while it is dequeued and keeping its maximum gives the answer in one pass.

Approach

  1. If the tree is empty, return an empty array.
  2. Put the root in a queue. While the queue is not empty, let size be its length.
  3. Dequeue size nodes, tracking the largest value among them and enqueuing their children.
  4. Append that row's largest value to the answer.

Why it works

At the start of each batch the queue holds exactly the nodes of one row — the previous batch enqueued precisely the children of the row before — so each batch's maximum is that row's maximum.

Complexity

  • Time — O(n)
  • Space — O(w), the widest row — O(n) at worst

Pitfalls

  • Values can be -2^31; starting a row's maximum at 0 or at -1 gives wrong answers on all-negative rows.
  • Read the row size before the loop that dequeues it; the queue grows while the row is processed.
  • An empty tree returns an empty array.

Reference solution

Python

from typing import List, Optional

def largestValues(root: Optional[TreeNode]) -> List[int]:
    out = []
    level = [root] if root is not None else []
    while level:
        best = level[0].val
        nxt = []
        for node in level:
            if node.val > best:
                best = node.val
            if node.left is not None:
                nxt.append(node.left)
            if node.right is not None:
                nxt.append(node.right)
        out.append(best)
        level = nxt
    return out

Java

public static int[] largestValues(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    ArrayDeque<TreeNode> queue = new ArrayDeque<>();
    if (root != null) queue.add(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        int best = queue.peek().val;
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            best = Math.max(best, node.val);
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }
        out.add(best);
    }
    int[] res = new int[out.size()];
    for (int i = 0; i < res.length; i++) res[i] = out.get(i);
    return res;
}

C++

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

JavaScript

var largestValues = function(root) {
    var out = [];
    var level = root === null ? [] : [root];
    while (level.length > 0) {
        var best = level[0].val, next = [];
        for (var i = 0; i < level.length; i++) {
            var node = level[i];
            if (node.val > best) best = node.val;
            if (node.left !== null) next.push(node.left);
            if (node.right !== null) next.push(node.right);
        }
        out.push(best);
        level = next;
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)