algoadvance

You are given the root of a binary tree. For each level of the binary tree, find the largest value in each row and return them in a list.

Example:

Input: 

          1
         / \
        3   2
       / \   \  
      5   3   9 

Output: [1, 3, 9]

Note:

• The number of nodes in the tree will be in the range [0, 10^4].
• The node values will be in the range [-2^31, 2^31 - 1].

Clarifying Questions

1. Can the binary tree be empty?
   • Yes, it is possible for the binary tree to be empty. In that case, the output should be an empty list.
2. Are the tree nodes always unique in value?
   • No, the tree nodes may contain duplicate values.
3. Should the solution handle large trees efficiently?
   • Yes, the solution should be efficient enough to handle the maximum possible number of nodes, which is (10^4).
4. Is there a maximum depth for the binary tree?
   • No specific maximum depth is provided other than the constraint on the number of nodes.

Strategy

We will use a breadth-first search (BFS) approach to traverse the tree level by level:

1. Initialize a queue to hold nodes to be processed, starting with the root node.
2. For each level:
   • Track the maximum value encountered.
   • Add all of the next level’s nodes to the queue.
3. Continue until all levels have been processed.
4. Return the list of maximum values for each level.

Code

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 largestValues(root: TreeNode) -> list:
    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

Time Complexity

• Time Complexity: (O(N)), where (N) is the number of nodes in the binary tree. This is because each node is processed once.
• Space Complexity: (O(D)), where (D) is the maximum width of the tree. This is the maximum number of nodes that can be held in the queue at any level during the BFS traversal. The width of the tree could be up to (N/2) in the worst case for a balanced tree, but typically it will be much less than (N).

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?