Given the root of a binary tree, return the maximum average value of a subtree of that tree. Answers within 10-5 of the actual answer will be accepted.
A subtree of a tree is any node of that tree plus all its descendants.
The average value of a tree is the sum of its values, divided by the number of nodes.
Example 1:
Input: root = [5,6,1] Output: 6.00000 Explanation: For the node with value = 5 we have an average of (5 + 6 + 1) / 3 = 4. For the node with value = 6 we have an average of 6 / 1 = 6. For the node with value = 1 we have an average of 1 / 1 = 1. So the answer is 6 which is the maximum.
Example 2:
Input: root = [0,null,1] Output: 1.00000
Constraints:
[1, 104].0 <= Node.val <= 105Problem Overview: You are given the root of a binary tree. For every possible subtree, compute its average value (sum of nodes divided by number of nodes). The goal is to return the maximum average among all subtrees.
Approach 1: Brute Force Subtree Recalculation (O(n²) time, O(h) space)
The direct idea is to treat every node as the root of a subtree and compute the subtree's total sum and node count. A helper DFS walks through the subtree to calculate these values, then you compute average = sum / count. This process repeats for every node in the tree. Because each subtree traversal may visit many nodes again, the total cost becomes quadratic in the worst case. Space complexity is O(h) due to recursion stack depth, where h is the tree height.
This approach demonstrates the core idea but wastes work by recomputing subtree information multiple times.
Approach 2: Postorder DFS with Aggregation (O(n) time, O(h) space)
The optimal solution uses a single postorder traversal of the tree. During DFS, each recursive call returns two values: the sum of the subtree and the number of nodes. With these values from the left and right children, you compute the current node’s subtree sum and size. The average for that subtree is sum / count, and you update a global maximum if the value is larger.
This works because a postorder traversal guarantees that both children are processed before their parent. Each node contributes its values exactly once, eliminating redundant computations. The algorithm runs in O(n) time since every node is visited once. The recursion stack requires O(h) space.
The technique is a classic pattern when solving problems on trees: return aggregated values from children and compute results at the parent. It combines ideas from depth-first search and structural recursion on a binary tree.
Recommended for interviews: The postorder DFS approach is what interviewers expect. Starting with the brute force idea shows you understand the problem, but optimizing it with aggregated DFS demonstrates strong tree recursion skills and reduces complexity from O(n²) to O(n).
We can use a recursive method. For each node, we calculate the sum and count of the nodes in the subtree rooted at that node, then calculate the average, compare it with the current maximum, and update the maximum if necessary.
Therefore, we design a function dfs(root) that represents the sum and count of nodes in the subtree rooted at root. The return value is an array of length 2, where the first element represents the sum of nodes, and the second element represents the count of nodes.
The recursive process of the function dfs(root) is as follows:
root is null, return [0, 0];root, denoted as [ls, ln]; calculate the sum and count of nodes in the right subtree of root, denoted as [rs, rn]. The sum of nodes in the subtree rooted at root is root.val + ls + rs, and the count of nodes is 1 + ln + rn. Calculate the average, compare it with the current maximum, and update the maximum if necessary;[root.val + ls + rs, 1 + ln + rn].Finally, return the maximum value.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subtree Traversal | O(n²) | O(h) | Useful for understanding the problem or when tree size is very small |
| Postorder DFS Aggregation | O(n) | O(h) | General case and optimal interview solution for computing subtree metrics |
LeetCode 1120 Maximum Average Subtree • leetuition • 4,086 views views
Watch 9 more video solutions →Practice Maximum Average Subtree with our built-in code editor and test cases.
Practice on FleetCode