Maximum Average Subtree

medium binary tree dfs post-order

Problem

Given the root of a binary tree, return the maximum average value of any subtree of that tree. A subtree of a node consists of that node together with all of its descendants. The average value of a subtree is the sum of all its node values divided by the number of those nodes.

Inputroot = [5, 6, 1]

Output6.00000

The whole tree averages (5 + 6 + 1) / 3 = 4. The single node 6 averages 6, the single node 1 averages 1. The largest average is 6.

tree (level-order, comma-separated, use "null" for gaps)

def maximum_average_subtree(root):
    best = 0.0
    def dfs(node):
        nonlocal best
        if not node:
            return (0, 0)
        ls, lc = dfs(node.left)
        rs, rc = dfs(node.right)
        s = ls + rs + node.val
        c = lc + rc + 1
        best = max(best, s / c)
        return (s, c)
    dfs(root)
    return best

function maximumAverageSubtree(root) {
  let best = 0;
  function dfs(node) {
    if (!node) return [0, 0];
    const [ls, lc] = dfs(node.left);
    const [rs, rc] = dfs(node.right);
    const s = ls + rs + node.val;
    const c = lc + rc + 1;
    best = Math.max(best, s / c);
    return [s, c];
  }
  dfs(root);
  return best;
}

class Solution {
    double best = 0;
    public double maximumAverageSubtree(TreeNode root) {
        dfs(root);
        return best;
    }
    private int[] dfs(TreeNode node) {
        if (node == null) return new int[]{0, 0};
        int[] l = dfs(node.left);
        int[] r = dfs(node.right);
        int s = l[0] + r[0] + node.val;
        int c = l[1] + r[1] + 1;
        best = Math.max(best, (double) s / c);
        return new int[]{s, c};
    }
}

class Solution {
public:
    double best = 0;
    double maximumAverageSubtree(TreeNode* root) {
        dfs(root);
        return best;
    }
    pair<int, int> dfs(TreeNode* node) {
        if (!node) return {0, 0};
        auto l = dfs(node->left);
        auto r = dfs(node->right);
        int s = l.first + r.first + node->val;
        int c = l.second + r.second + 1;
        best = max(best, (double) s / c);
        return {s, c};
    }
};

Explanation

An average is just a sum divided by a count, so if every subtree could quickly tell us its total value and how many nodes it has, computing its average is trivial. We get both with one post-order DFS.

Each call returns a pair (sum, count) for the subtree rooted at that node. For a missing child we return (0, 0), which contributes nothing.

At a real node we combine the children: s = ls + rs + node.val and c = lc + rc + 1. Then we compute this subtree's average s / c and update a global best if it is larger. Finally we return (s, c) so the parent can build on it.

Because we add up child sums and counts instead of recomputing them, every node is processed once, giving an O(n) pass.

Example: [5, 6, 1]. The whole tree averages 12 / 3 = 4, but the lone node 6 averages 6 / 1 = 6, which is the highest, so the answer is 6.

Time: O(n) Space: O(h)