Code Implementation

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def largestValues(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        from collections import deque
        queue = deque([root])
        result = []
        while queue:
            level_size = len(queue)
            max_val = float('-inf')
            for _ in range(level_size):
                node = queue.popleft()
                max_val = max(max_val, node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            result.append(max_val)
        return result
      

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        vector<int> result;
        if (!root) return result;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int levelSize = q.size();
            int maxVal = INT_MIN;
            for (int i = 0; i < levelSize; ++i) {
                TreeNode* node = q.front(); q.pop();
                if (node->val > maxVal) maxVal = node->val;
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            result.push_back(maxVal);
        }
        return result;
    }
};
      

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
import java.util.*;
class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            int maxVal = Integer.MIN_VALUE;
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                maxVal = Math.max(maxVal, node.val);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            result.add(maxVal);
        }
        return result;
    }
}
      

/**
 * 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 largestValues = function(root) {
    if (!root) return [];
    let queue = [root];
    const result = [];
    while (queue.length > 0) {
        let levelSize = queue.length;
        let maxVal = -Infinity;
        for (let i = 0; i < levelSize; i++) {
            let node = queue.shift();
            maxVal = Math.max(maxVal, node.val);
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        result.push(maxVal);
    }
    return result;
};
      

Problem Description

You are given the root node of a binary tree. Your task is to find the largest value in each row (or level) of the tree. The tree may be empty, in which case you should return an empty list.

• Each row of the tree corresponds to all nodes at a particular depth, starting with the root at depth 0.
• You must return a list containing the largest value found at each level, from top to bottom.
• The input is provided as a binary tree node structure, typically called root.
• If the tree is empty (root is null), return an empty list.

Thought Process

To solve this problem, we need to consider how to efficiently visit all nodes in the tree, grouped by their level. The most natural way to process nodes level by level is to use a Breadth-First Search (BFS), which visits all nodes at one depth before moving to the next.

A brute-force approach would be to traverse the tree and, for each node, keep track of its depth and collect values in a dictionary or list by depth. After traversal, we could find the max in each list. However, this is unnecessarily complex since BFS naturally groups nodes by level.

The optimized approach is to use a queue to process nodes level by level. At each level, we track the maximum value seen and add it to the result. This avoids extra data structures and makes the solution both clean and efficient.

Solution Approach

• Step 1: Check if the root is null. If so, return an empty list because there are no levels to process.
• Step 2: Initialize a queue and add the root node to it. This queue will help us process nodes level by level (BFS).
• Step 3: While the queue is not empty, repeat the following:
  • Determine how many nodes are at the current level (the queue's length).
  • Initialize a variable to keep track of the maximum value at this level, starting with negative infinity.
  • For each node at this level:
    • Remove the node from the queue.
    • Update the maximum value if this node's value is greater.
    • Add the node's left and right children (if any) to the queue for the next level.
  • After processing all nodes at this level, append the maximum value found to the result list.
• Step 4: Once all levels are processed, return the result list containing the largest value from each row.

We use a queue for BFS because it allows us to efficiently process nodes in the order they appear at each level. Tracking the maximum value per level is straightforward since we know how many nodes to process at each step.

Example Walkthrough

Consider the following binary tree:

         1
        / \
       3   2
      / \   \
     5   3   9
  

Let's walk through the steps:

• Level 0: Only node 1. Largest value is 1.
• Level 1: Nodes 3 and 2. Largest value is 3.
• Level 2: Nodes 5, 3, and 9. Largest value is 9.

The output will be [1, 3, 9].

At each level, we process all nodes, update the maximum, and add their children to the queue for the next level.

Time and Space Complexity

• Brute-force approach:
  • Time Complexity: O(N), where N is the number of nodes (since each node is visited once).
  • Space Complexity: O(N), due to storing all values per level before finding the max.
• Optimized BFS approach (the one above):
  • Time Complexity: O(N), because every node is visited exactly once.
  • Space Complexity: O(W), where W is the maximum width of the tree (the largest number of nodes at any level), which is the maximum queue size at any time.

The BFS approach is optimal for this problem, as it processes each node only once and uses space proportional to the tree's width.

Summary

To find the largest value in each row of a binary tree, we use a breadth-first search (BFS) to process nodes level by level. At each level, we track and record the maximum value. This approach is both intuitive and efficient, leveraging the natural structure of the tree and the properties of BFS. The solution is elegant because it requires only a simple queue and a single pass through the tree, making it easy to understand and implement.