Maximum Average Subtree

Maximum Average Subtree

What is this problem about?

In the Maximum Average Subtree problem, you are given the root of a binary tree. The "average" of a subtree is the sum of all its node values divided by the total number of nodes in that subtree. A subtree includes a specific node and all of its descendants. Your goal is to calculate the average for every possible subtree and return the maximum average value found.

Why is this asked in interviews?

This is a textbook Post-Order Tree Traversal problem. Interviewers ask it because calculating an average requires two distinct pieces of information: a sum and a count. It tests a candidate's ability to create a custom data structure (or array) to pass multiple pieces of state up a recursive call stack, avoiding redundant $O(N^2)$ calculations.

Algorithmic pattern used

This problem uses Depth-First Search (Post-Order Traversal).

1. The recursive DFS function needs to return an object or an array [sum, count] for the current subtree.
2. For any given node, you recursively call DFS on the left child and right child.
3. The total_sum for the current node is node.val + left.sum + right.sum.
4. The total_count for the current node is 1 + left.count + right.count.
5. Calculate the current average: (double) total_sum / total_count. Update a global max_average variable if this is the highest seen so far.
6. Return [total_sum, total_count] to the parent.

Example explanation

Tree:

    5
   / \
  6   1

DFS starts at root 5.

• Recurse left to 6. It's a leaf.
  • Sum = 6, Count = 1. Average = 6.0. max_avg = 6.0. Returns [6, 1].
• Recurse right to 1. It's a leaf.
  • Sum = 1, Count = 1. Average = 1.0. max_avg remains 6.0. Returns [1, 1].
• Back at root 5:
  • total_sum = $5 + 6 + 1 = 12$.
  • total_count = $1 + 1 + 1 = 3$.
  • Average = $12 / 3 = 4.0$.
  • max_avg remains 6.0. The maximum average subtree is the one rooted at 6, with an average of 6.0.

Common mistakes candidates make

A frequent mistake is writing a helper function that calculates the sum, another helper that calculates the count, and calling both on every node. This top-down approach recalculates the same subtrees repeatedly, resulting in an $O(N^2)$ time complexity. By passing the state upwards (bottom-up), each node is visited exactly once, yielding an optimal $O(N)$ solution. Also, watch out for integer division! You must cast the sum to a double before dividing.

Interview preparation tip

When an interview question requires you to compute a metric based on multiple properties of a subtree (like sum AND count, or min AND max), immediately define a custom State class (e.g., class State { int sum; int count; }) or return an int[]. Returning these objects from your post-order DFS is the cleanest way to orchestrate complex tree aggregations.