We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find Largest Value in Each Tree Row

Difficulty: Medium

Problem Description

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

Key Insights

  • We need to traverse each level of the binary tree.
  • We can use either Breadth-First Search (BFS) or Depth-First Search (DFS) to explore the tree.
  • As we traverse each level, we keep track of the maximum value encountered at that level.
  • The final result is a list of these maximum values for each level.

Space and Time Complexity

Time Complexity: O(n) - where n is the number of nodes in the tree, as each node is visited once. Space Complexity: O(m) - where m is the maximum number of nodes at any level of the tree, which can occur in the queue for BFS.

Solution

To solve this problem, we can employ a Breadth-First Search (BFS) approach using a queue. We will initialize a queue with the root node and then iteratively process each level of the tree. For each level, we will determine the maximum value and store it in a results list. The algorithm will continue until all levels of the tree have been processed.

Code Solutions

from collections import deque

def largestValues(root):
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level_size = len(queue)
        max_value = float('-inf')
        
        for _ in range(level_size):
            node = queue.popleft()
            max_value = max(max_value, node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(max_value)
    
    return result
← Back to All Questions