Maximum Average Subtree

Medium · Graphs · Explanation and code example

Postorder Traversal

How it works

To find the subtree with the maximum average, we need to know each subtree's sum and node count. A key observation is that a subtree's values depend entirely on its children's values. This makes postorder traversal the natural choice: we process children first, then use their results to compute the parent's values.

For each node, we track three things: the number of nodes in its subtree, the sum of values in its subtree, and the maximum average found so far. By bubbling these values up from leaves to the root, we can compute the average at every node and keep track of the best one.

Steps

  1. Define a helper structure State to hold three values: nodeCount, valueSum, and maxAverage.
  2. Perform a postorder traversal using recursion:
    • Base case: if the node is null, return a state with all zeros.
    • Recursively process the left and right children.
    • Compute the current node's count as left.nodeCount + right.nodeCount + 1.
    • Compute the current node's sum as left.valueSum + right.valueSum + node.val.
    • Compute the current subtree's average and compare it with the maximum averages from both children.
  3. Return the maxAverage from the root's state.

Complexity

  • Time complexity: O(N)
  • Space complexity: O(N)

Where N is the number of nodes in the tree

Things to watch for

Using Preorder Instead of Postorder

Computing a subtree's average requires knowing the sum and count of all nodes in that subtree. Preorder traversal visits the parent before children, so you would not have the children's information when processing the parent. Postorder ensures children are processed first.

Integer Division Truncation

When computing the average, dividing two integers truncates the decimal part in many languages. Always cast to floating-point before division (e.g., 1.0 * sum / count) to get the correct average value.

Forgetting to Include the Current Node

When aggregating values from children, you must add the current node's value and count it as well. A subtree rooted at a node includes that node itself, not just its descendants.

Python code example

from typing import Optional

class Solution:
    # for each node in the tree, we will maintain three values
    class State:
        def __init__(self, nodes, sum_val, max_average):
            # count of nodes in the subtree
            self.node_count = nodes
            # sum of values in the subtree
            self.value_sum = sum_val
            # max average found in the subtree
            self.max_average = max_average

    def maximumAverageSubtree(self, root: Optional[TreeNode]) -> float:
        return self.max_average(root).max_average

    def max_average(self, root):
        if root is None:
            return self.State(0, 0, 0)

        # postorder traversal, solve for both child nodes first.
        left = self.max_average(root.left)
        right = self.max_average(root.right)

        # now find nodeCount, valueSum and maxAverage for current node `root`
        node_count = left.node_count + right.node_count + 1
        sum_val = left.value_sum + right.value_sum + root.val
        max_average = max(
            (1.0 * sum_val) / node_count,  # average for current node
            max(right.max_average, left.max_average)  # max average from child nodes
        )

        return self.State(node_count, sum_val, max_average)

C++ code example

class Solution {
public:
    double maximumAverageSubtree(TreeNode* root) {
        return maxAverage(root).maxAverage;
    }

private:
    struct State {
        // count of nodes in the subtree
        int nodeCount;

        // sum of values in the subtree
        int valueSum;

        // max average found in the subtree
        double maxAverage;
    };

    State maxAverage(TreeNode* root) {
        if (!root) return {0, 0, 0};

        // postorder traversal, solve for both child nodes first.
        State left = maxAverage(root->left);
        State right = maxAverage(root->right);

        // now find nodeCount, valueSum and maxAverage for current node `root`
        int nodeCount = left.nodeCount + right.nodeCount + 1;
        int sum = left.valueSum + right.valueSum + root->val;
        double maxAverage = max(
                (1.0 * (sum)) / nodeCount, // average for current node
                max(right.maxAverage, left.maxAverage) // max average from child nodes
        );

        return {nodeCount, sum, maxAverage};
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations