Maximum Average Subtree solution and explanation
9 more videos on this problem
LeetCode 1120 Maximum Average Subtreeleetuition · 12:17 · 4K views
1120. Maximum Average Subtree (LeetCode)hakunamatasq · 5:42 · 1K views
1120. Maximum Average Subtree (Biweekly Contest 4)Kelvin Chandra · 3:27 · 1K views
米开：LeetCode 1120. Maximum Average SubtreeM.C米开朗基罗 · 4:36 · 662 views
Facebook Coding Interview Question | Leetcode 1120 | Maximum Average SubtreeWorkWithGoogler · 7:35 · 397 views
1120. Maximum Average SubtreeData Structures & Algorithms Learning · 4:53 · 388 views
1120. Maximum Average Subtree - Week 2/5 Leetcode December ChallengeProgramming Live with Larry · 3:21 · 155 views
Maximum Average Subtree - LeetCode 1120 - PythonAlpha-Code · 9:20 · 98 views
leetcode 1120. Maximum Average Subtree - RecursionCode-Yao · 9:08 · 98 views
Code Review: LeetCode #1120 Maximum Average Subtree (Python) (2 Solutions!!)Roel Van de Paar · 3:51 · 27 views
The problem
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:
- The number of nodes in the tree is in the range
[1, 104]. 0 <= Node.val <= 105
Approach overview
Problem 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).
Solution
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:
- If
rootis null, return[0, 0]; - Otherwise, calculate the sum and count of nodes in the left subtree of
root, denoted as[ls, ln]; calculate the sum and count of nodes in the right subtree ofroot, denoted as[rs, rn]. The sum of nodes in the subtree rooted atrootisroot.val + ls + rs, and the count of nodes is1 + ln + rn. Calculate the average, compare it with the current maximum, and update the maximum if necessary; - Return
[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.
# 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
class Solution:
def maximumAverageSubtree(self, root: Optional[TreeNode]) -> float:
def dfs(root):
if root is None:
return 0, 0
ls, ln = dfs(root.left)
rs, rn = dfs(root.right)
s = root.val + ls + rs
n = 1 + ln + rn
nonlocal ans
ans = max(ans, s / n)
return s, n
ans = 0
dfs(root)
return ans/**
* 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;
* }
* }
*/
class Solution {
private double ans;
public double maximumAverageSubtree(TreeNode root) {
dfs(root);
return ans;
}
private int[] dfs(TreeNode root) {
if (root == null) {
return new int[2];
}
var l = dfs(root.left);
var r = dfs(root.right);
int s = root.val + l[0] + r[0];
int n = 1 + l[1] + r[1];
ans = Math.max(ans, s * 1.0 / n);
return new int[] {s, n};
}
}/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
double maximumAverageSubtree(TreeNode* root) {
double ans = 0;
auto dfs = [&](this auto&& dfs, TreeNode* root) -> pair<int, int> {
if (!root) {
return {0, 0};
}
auto [ls, ln] = dfs(root->left);
auto [rs, rn] = dfs(root->right);
int s = root->val + ls + rs;
int n = 1 + ln + rn;
ans = max(ans, s * 1.0 / n);
return {s, n};
};
dfs(root);
return ans;
}
};/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func maximumAverageSubtree(root *TreeNode) (ans float64) {
var dfs func(*TreeNode) [2]int
dfs = func(root *TreeNode) [2]int {
if root == nil {
return [2]int{}
}
l, r := dfs(root.Left), dfs(root.Right)
s := root.Val + l[0] + r[0]
n := 1 + l[1] + r[1]
ans = math.Max(ans, float64(s)/float64(n))
return [2]int{s, n}
}
dfs(root)
return
}Complexity analysis
| 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 |
Frequently asked questions
Is Maximum Average Subtree easy or hard?
Maximum Average Subtree is generally classified as a Medium problem. The challenge is recognizing that subtree sum and node count can be computed during a single postorder traversal instead of recomputing them for every node.
Maximum Average Subtree Python/Java solution
Most implementations use a recursive helper that returns (sum, count) for each subtree and updates a global maximum average. The same logic works across Python, Java, C++, and Go with identical O(n) time complexity.
How to solve Maximum Average Subtree in O(n)?
Use a postorder DFS that returns two values for every node: subtree sum and subtree size. Combine results from the left and right children, compute the current subtree average, and update a global maximum. Since each node is processed once, the algorithm runs in O(n).
What is the best approach for Maximum Average Subtree?
The best approach is a postorder depth-first search that returns the sum and node count of each subtree. With these values you compute the average at every node and track the maximum. This processes each node once, giving O(n) time and O(h) recursion space.
Is Maximum Average Subtree asked at Google/Amazon/Meta?
Tree DFS aggregation problems similar to Maximum Average Subtree frequently appear in interviews at companies like Amazon, Meta, and Google. Interviewers use them to evaluate recursion, tree traversal, and ability to compute values bottom-up.
What data structure is used in Maximum Average Subtree?
The primary data structure is a binary tree. The algorithm relies on depth-first search recursion where each call returns aggregated values such as subtree sum and node count.
What is the time complexity of Maximum Average Subtree?
The optimal solution runs in O(n) time because each node in the binary tree is visited exactly once during the DFS traversal. The recursion stack requires O(h) space where h is the height of the tree.