Maximum Value in Each Level of Binary Tree

Given a binary tree, return the largest value in each of its levels.

Example(s)

Example 1:

Tree:
    2
   / \
  10  15
       \
        20
Output: [2,15,20]

Example 2:

Tree:
          1
         / \
        5   6
       / \   \  
      5   3   7 
Output: [1,6,7]

Solution

JavaScript Solution

/**
 * 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)
 * }
 */

/**
 * Find maximum value in each level of a binary tree
 * @param {TreeNode} root - Root of the binary tree
 * @return {number[]} - Array of maximum values per level
 */
function largestValues(root) {
  if (!root) return [];
  
  const result = [];
  const queue = [root];
  
  while (queue.length) {
    const levelSize = queue.length;
    let maxVal = -Infinity;
    
    for (let i = 0; i < levelSize; i++) {
      const 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;
}

Python Solution

from typing import Optional, List
from collections import deque

# 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

def largest_values(root: Optional[TreeNode]) -> List[int]:
    """
    Find maximum value in each level of a binary tree
    
    Args:
        root: Root of the binary tree
        
    Returns:
        List[int]: Array of maximum values per level
    """
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    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

Complexity

• Time Complexity: O(n) - Where n is the number of nodes in the tree
• Space Complexity: O(w) - Where w is the maximum width of the tree

Approach

The solution uses a breadth-first search (BFS) approach:

1. Level-by-level traversal using a queue
2. Track level size to process all nodes at each level
3. Find maximum value at each level
4. Return array of maximum values per level

Key Insights

• Breadth-first search ensures level-by-level processing to find maximum values
• Queue data structure efficiently handles node traversal in order
• Level separation achieved by tracking level size for accurate maximum computation
• Edge cases include empty tree, single-node tree, and negative values
• O(n) time is optimal as all nodes must be visited to determine level maximums