LeetCode Solutions Blog

Find Largest Value in Each Tree Row

Number: 515

Difficulty: Medium

Paid? No

Problem Description

Given the root of a binary tree, return an array containing the largest value in each row (level) of the tree. Each level's maximum should be computed by comparing all node values present in that particular row.

Key Insights

Use a level-order traversal (BFS) to iterate through the tree level by level.
For each level, track the maximum value encountered among all nodes.
Edge case: If the tree is empty, return an empty array.
Efficiently process nodes by using a queue data structure for BFS.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes, since each node is visited once. Space Complexity: O(n), in the worst-case scenario when the tree is completely unbalanced (or when storing all nodes of the bottom level in the queue).

Solution

We perform a breadth-first search (BFS) using a queue to process the tree level by level. For each level, we initialize a variable to track the maximum value, iterate through all nodes at that level, and update this variable as needed. After processing a level, we add the found maximum to our result list. Finally, we return the result list which contains the largest value from each level.

Code Solutions

from collections import deque

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val       # Node's value
        self.left = left     # Left child
        self.right = right   # Right child

class Solution:
    def largestValues(self, root: TreeNode) -> list:
        if not root:
            return []  # Return empty list if tree is empty
        
        result = []             # List to hold the largest value per row
        queue = deque([root])   # Initialize queue with the root node
        
        while queue:
            level_size = len(queue)  # Number of nodes at the current level
            max_value = float('-inf')  # Initialize max_value to the smallest possible number
            
            # Process all nodes for the current level
            for _ in range(level_size):
                node = queue.popleft()           # Get the next node
                max_value = max(max_value, node.val)  # Update max_value
                
                # Add left child if exists
                if node.left:
                    queue.append(node.left)
                # Add right child if exists
                if node.right:
                    queue.append(node.right)
            
            result.append(max_value)  # Append the largest value in this level
        
        return result