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.

Description Hints 3 Solution Video 12:17

1120. Maximum Average Subtree

Medium66.7% acceptance1 companyPremium elsewhere, free here

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, 10⁴].
0 <= Node.val <= 10⁵

Asked at 1 company

Amazon

Topics

Hints open one at a time

Hint 1

Can you find the sum of values and the number of nodes for every sub-tree ?

Hint 2

Can you find the sum of values and the number of nodes for a sub-tree given the sum of values and the number of nodes of it's left and right sub-trees ?

Hint 3

Use depth first search to recursively find the solution for the children of a node then use their solutions to compute the current node's solution.

12:17

Still stuck?Read the written solution, or watch a walkthrough.

Open solution