Maximum Average Subtree

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

private:
    struct Stats {
        int totalNodes;
        int totalSum;
        double maxAverage;
    };

    Stats computeStats(TreeNode* root) {
        if (!root) return {0, 0, 0};

        Stats leftStat = computeStats(root->left);
        Stats rightStat = computeStats(root->right);

        int totalNodes = leftStat.totalNodes + rightStat.totalNodes + 1;
        int totalSum = leftStat.totalSum + rightStat.totalSum + root->val;
        double maxAve = max(
                (double(totalSum) / totalNodes),
                max(leftStat.maxAverage, rightStat.maxAverage)
        );

        return {totalNodes, totalSum, maxAve};
    }
};

To address the problem of finding the maximum average value of any subtree in a binary tree, you'll use a C++ program that defines a Solution class with methods to compute and return this maximum average. The approach involves defining a nested structure Stats that holds three properties for each subtree:

• totalNodes - the count of nodes in the subtree
• totalSum - the sum of all node values in the subtree
• maxAverage - the highest average computed within this subtree or its children

Follow these steps to compute the maximum average:

1. Create a recursive function computeStats that returns a Stats object for any given node. This function checks if the current node is null, and if so, returns a Stats object initialized to {0, 0, 0}.

2. If the node is not null, the function recursively computes Stats for both the left and right children of the current node.

3. Using returned statistics from both children, calculate the totalNodes and totalSum for the current subtree including the current node.

4. Determine maxAverage by comparing the average of the current subtree with the maximum averages returned from the left and right subtrees. Use the formula: [ maxAve = max\left(\frac{totalSum}{totalNodes}, max(leftStat.maxAverage, rightStat.maxAverage)\right) ]

5. Return a Stats object for the current node with values populated as computed.

The main function, findMaxAverageSubtree, simply invokes the computeStats on the root of the entire tree and returns the maxAverage part of the result. With this method, navigating through the tree and calculating required values, you ensure efficient computation with optimal tree traversal.

class Solution {
    class SubtreeData {
        int totalNodes;
        int sumValues;
        double highestAvg;

        SubtreeData(int count, int sum, double maxAvg) {
            this.totalNodes = count;
            this.sumValues = sum;
            this.highestAvg = maxAvg;
        }
    }

    public double maximumAverageSubtree(TreeNode root) {
        return computeMaxAvg(root).highestAvg;
    }

    SubtreeData computeMaxAvg(TreeNode root) {
        if (root == null) {
            return new SubtreeData(0, 0, 0);
        }

        SubtreeData leftSubtree = computeMaxAvg(root.left);
        SubtreeData rightSubtree = computeMaxAvg(root.right);

        int totalCount = leftSubtree.totalNodes + rightSubtree.totalNodes + 1;
        int totalSum = leftSubtree.sumValues + rightSubtree.sumValues + root.val;
        double currentMaxAvg = Math.max(
                (double) totalSum / totalCount,
                Math.max(leftSubtree.highestAvg, rightSubtree.highestAvg)
        );

        return new SubtreeData(totalCount, totalSum, currentMaxAvg);
    }
}

In the given Java solution, the problem of finding the maximum average value of any subtree in a binary tree is addressed using a recursion-based approach. The solution involves the creation of a helper class, SubtreeData, to store three pieces of information for each subtree:

• totalNodes - the total number of nodes in the subtree.
• sumValues - the sum of the values of the nodes in the subtree.
• highestAvg - the highest average found in the subtree.

The primary method maximumAverageSubtree(TreeNode root) initiates the recursive process by calling another method computeMaxAvg(TreeNode root), which returns a SubtreeData instance representing the entire tree starting from the root.

The recursive function computeMaxAvg(TreeNode root) follows these steps:

1. If the current node (root) is null, return a new SubtreeData object initialized to zero values, representing an empty subtree.
2. Recursively compute the subtree data for the left child of the current node using computeMaxAvg(root.left).
3. Recursively compute the subtree data for the right child of the current node using computeMaxAvg(root.right).
4. Calculate the total count and sum of nodes' values for the current subtree, including the current node's value.
5. Compute the average value of the current subtree, then determine the highest average by comparing this average with the maximum averages from the left and right subtrees.
6. Return a new SubtreeData object for the current subtree, containing the freshly calculated total count, total sum, and highest average.

This approach ensures that each subtree's maximum average is considered, efficiently finding the maximum average across all possible subtrees of the binary tree.