Find Largest Value in Each Tree Row

LeetCode 515: Find Largest Value in Each Tree Row Solution & Explanation

Problem Overview

TL;DR: The optimal solution uses Breadth-First Search (BFS) to traverse the tree level by level, tracking the maximum value encountered within the current batch of nodes representing a specific row.

The Find Largest Value in Each Tree Row problem requires us to process a binary tree and identify the single highest numerical value present at every depth level. If a tree has a height of $H$, the output will be an array of size $H$, where the $i$-th element corresponds to the maximum value found among all nodes at depth $i$.

This is a classic tree traversal challenge that tests the ability to aggregate data horizontally across a tree structure. It is a popular interview question for companies like Facebook, often used to verify a candidate's grasp of standard traversal algorithms.

Brute Force Approach for Find Largest Value in Each Tree Row

A naive approach to solving Find Largest Value in Each Tree Row might involve traversing the tree repeatedly or using an inefficient storage mechanism.

One specific brute-force strategy is to perform a separate traversal for every possible depth level. For a tree of height $H$:

1. Start at depth $d = 0$.
2. Traverse the entire tree from the root.
3. Check every node's depth. If it matches $d$, consider it for the maximum.
4. Increment $d$ and repeat until $d == H$.

Pseudo-code

function findLargestValues(root):
    height = getHeight(root)
    result = []
    
    for d from 0 to height - 1:
        max_val = -infinity
        // Traverse entire tree to find nodes at depth d
        nodes = getAllNodesAtDepth(root, d) 
        for node in nodes:
            max_val = max(max_val, node.val)
        result.add(max_val)
        
    return result

Complexity Analysis

The time complexity of this approach is $O(N \times H)$, where $N$ is the number of nodes and $H$ is the height of the tree.

• In the worst case (a skewed tree), $H \approx N$, resulting in $O(N^2)$ complexity.
• In a balanced tree, $H \approx \log N$, resulting in $O(N \log N)$.

Why it fails

This approach is inefficient because it revisits nodes unnecessarily. To find nodes at depth 3, we must traverse through depth 0, 1, and 2 again. While this might pass for small constraints, it demonstrates a lack of understanding regarding state maintenance during traversal. A single-pass solution is expected in interviews.

Algorithm Strategy: Tree BFS - Level Order Traversal

1. Initialization: Create a result list and a Queue. If the root is null, return the empty list immediately.
2. Bootstrap: Add the root node to the Queue.
3. Outer Loop: Continue while the Queue is not empty.
   • Snapshot Size: Store n = queue.size(). This n represents the number of nodes in the current row.
   • Level Max: Initialize a variable max_val to the smallest possible integer (e.g., Integer.MIN_VALUE).
   • Inner Loop: Iterate n times:
     • Dequeue a node.
     • Update max_val with the maximum of itself and the node's value.
     • Enqueue the node's left and right children (if they exist).
   • Store Result: After the inner loop finishes, append max_val to the result list.
4. Completion: Return the result list.

Execution Flow

Let's trace the algorithm with Input: root = [1, 3, 2].

1. Start: Queue = [1], Result = [].
2. Level 0:
   • Queue size is 1.
   • max_val initialized to MIN_INT.
   • Process Node 1:
     • Pop 1.
     • max_val becomes 1.
     • Push children 3 and 2. Queue = [3, 2].
   • End of level. Result = [1].
3. Level 1:
   • Queue size is 2.
   • max_val initialized to MIN_INT.
   • Process Node 3:
     • Pop 3.
     • max_val becomes 3.
     • No children. Queue = [2].
   • Process Node 2:
     • Pop 2.
     • max_val remains 3 (since 3 > 2).
     • No children. Queue = [].
   • End of level. Result = [1, 3].
4. End: Queue is empty. Return [1, 3].

Proof of Correctness

The correctness relies on the FIFO (First-In-First-Out) property of the Queue.

• Invariant: At the start of the outer loop iteration, the Queue contains all nodes at depth $L$ and no nodes from any other depth.
• Induction:
  • Base Case: Initially, the Queue contains only the root (Depth 0).
  • Step: Assuming the Queue contains only nodes at Depth $L$, the inner loop processes exactly those nodes. As we remove nodes at Depth $L$, we add their children, which are strictly at Depth $L+1$. By the time the inner loop finishes, all Depth $L$ nodes are removed, and all Depth $L+1$ nodes are added.
• Conclusion: The variable max_val is computed strictly over the set of values at Depth $L$, ensuring the correct maximum is found for each row.

Pattern Reuse Notes

The Tree BFS - Level Order Traversal pattern is highly reusable. The logic of "snapshotting" the queue size to process one level at a time is identical in the following problems:

• LeetCode 102: Binary Tree Level Order Traversal - Instead of finding the max, you simply collect all nodes into a sub-list.
• LeetCode 103: Binary Tree Zigzag Level Order Traversal - Same logic, but you reverse the order of addition for every other level.
• LeetCode 199: Binary Tree Right Side View - Instead of the max, you only capture the last node processed in the inner loop.
• LeetCode 1161: Maximum Level Sum of a Binary Tree - Instead of max node value, you calculate the sum of the level and track which level has the highest sum.

Reference Implementation

C++ Solution for LeetCode 515

1#include <vector>
2#include <queue>
3#include <algorithm>
4#include <climits>
5
6using namespace std;
7
8struct TreeNode {
9    int val;
10    TreeNode *left;
11    TreeNode *right;
12    TreeNode() : val(0), left(nullptr), right(nullptr) {}
13    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
14    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
15};
16
17class Solution {
18public:
19    vector<int> largestValues(TreeNode* root) {
20        vector<int> result;
21        if (!root) {
22            return result;
23        }
24
25        queue<TreeNode*> q;
26        q.push(root);
27
28        while (!q.empty()) {
29            int levelSize = q.size();
30            int maxVal = INT_MIN;
31
32            for (int i = 0; i < levelSize; ++i) {
33                TreeNode* currentNode = q.front();
34                q.pop();
35
36                maxVal = max(maxVal, currentNode->val);
37
38                if (currentNode->left) {
39                    q.push(currentNode->left);
40                }
41                if (currentNode->right) {
42                    q.push(currentNode->right);
43                }
44            }
45            result.push_back(maxVal);
46        }
47
48        return result;
49    }
50};

Java Solution for LeetCode 515

1import java.util.ArrayList;
2import java.util.LinkedList;
3import java.util.List;
4import java.util.Queue;
5
6/**
7 * Definition for a binary tree node.
8 * public class TreeNode {
9 *     int val;
10 *     TreeNode left;
11 *     TreeNode right;
12 *     TreeNode() {}
13 *     TreeNode(int val) { this.val = val; }
14 *     TreeNode(int val, TreeNode left, TreeNode right) {
15 *         this.val = val;
16 *         this.left = left;
17 *         this.right = right;
18 *     }
19 * }
20 */
21class Solution {
22    public List<Integer> largestValues(TreeNode root) {
23        List<Integer> result = new ArrayList<>();
24        if (root == null) {
25            return result;
26        }
27
28        Queue<TreeNode> queue = new LinkedList<>();
29        queue.offer(root);
30
31        while (!queue.isEmpty()) {
32            int levelSize = queue.size();
33            // Initialize with MIN_VALUE because node values can be negative
34            int maxVal = Integer.MIN_VALUE;
35
36            for (int i = 0; i < levelSize; i++) {
37                TreeNode currentNode = queue.poll();
38                maxVal = Math.max(maxVal, currentNode.val);
39
40                if (currentNode.left != null) {
41                    queue.offer(currentNode.left);
42                }
43                if (currentNode.right != null) {
44                    queue.offer(currentNode.right);
45                }
46            }
47            result.add(maxVal);
48        }
49
50        return result;
51    }
52}

Python Solution for LeetCode 515

1from collections import deque
2from typing import Optional, List
3
4# Definition for a binary tree node.
5# class TreeNode:
6#     def __init__(self, val=0, left=None, right=None):
7#         self.val = val
8#         self.left = left
9#         self.right = right
10
11class Solution:
12    def largestValues(self, root: Optional[TreeNode]) -> List[int]:
13        result = []
14        if not root:
15            return result
16        
17        queue = deque([root])
18        
19        while queue:
20            level_size = len(queue)
21            # Initialize with negative infinity
22            max_val = float('-inf')
23            
24            for _ in range(level_size):
25                node = queue.popleft()
26                max_val = max(max_val, node.val)
27                
28                if node.left:
29                    queue.append(node.left)
30                if node.right:
31                    queue.append(node.right)
32            
33            result.append(max_val)
34            
35        return result