algoadvance

Leetcode 515. Find Largest Value in Each Tree Row

Problem Statement

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

Clarifying Questions

1. Can the tree have negative values?
   • Yes, the tree can have negative values.
2. What should be returned if the tree is empty?
   • If the tree is empty, return an empty list.
3. Can the tree be unbalanced?
   • Yes, the tree can be unbalanced.
4. Is there a maximum tree depth we should consider for optimization?
   • No specific maximum depth is mentioned; the solution should handle general cases efficiently.

Strategy

1. Breadth-First Search (BFS):
   • Use a queue to perform a level-order traversal (BFS) of the tree.
   • At each level, traverse all nodes and keep track of the maximum value.
   • Append the maximum value of each level to the result list.
2. Depth-First Search (DFS):
   • Use a recursive approach to visit each node, keeping track of the current level.
   • Maintain a list where each index corresponds to a level’s maximum value.
   • Update the list when a new maximum value is found for a particular level.

For this solution, we’ll implement the BFS approach.

Code

import java.util.*;

public class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            int maxVal = Integer.MIN_VALUE;
            
            for (int i = 0; i < size; i++) {
                TreeNode currentNode = queue.poll();
                maxVal = Math.max(maxVal, currentNode.val);
                
                if (currentNode.left != null) queue.add(currentNode.left);
                if (currentNode.right != null) queue.add(currentNode.right);
            }
            
            result.add(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;
        }
    }
}

Time Complexity

• Time Complexity: O(N), where N is the number of nodes in the binary tree. Each node is visited once.
• Space Complexity: O(M), where M is the maximum number of nodes at any level in the tree (width of the tree). In the worst case (a completely balanced tree), this would be O(N/2) = O(N).

This approach efficiently finds the largest value in each row using level-order traversal, ensuring a straightforward and understandable implementation.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• 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?