Maximum Average Subtree

Naive Solution

The brute-force approach involves traversing every node in the tree and considering it as the root of a subtree. For each node, we calculate the sum of all nodes in its subtree and the number of nodes in that subtree. The average is then computed. We keep track of the maximum average found so far and return it.

This approach explores all possible subtrees, which is computationally expensive.

Big O Complexity

• Time Complexity: O(N^2), where N is the number of nodes in the tree. For each node, we potentially visit all its descendants to compute the sum and count, leading to a quadratic time complexity in the worst case (e.g., a skewed tree).
• Space Complexity: O(H), where H is the height of the tree. This is due to the recursion stack space used during the traversal. In the worst case (skewed tree), H can be N, resulting in O(N) space complexity. In the average case (balanced tree), H would be log(N), resulting in O(log(N)) space complexity.

Optimal Solution

A more efficient solution involves using a post-order traversal of the tree. During the post-order traversal, we calculate the sum and count of nodes in each subtree. We then calculate the average of each subtree and update the maximum average found so far. By doing this in a single traversal, we avoid redundant calculations.

Algorithm

1. Define a recursive function helper(node) that returns a tuple (sum, count) for the subtree rooted at node.
2. In the helper function:
   • If the node is null, return (0, 0). (Edge Case)
   • Recursively call helper on the left and right children to get their sums and counts.
   • Calculate the sum and count for the current subtree by adding the values from the left and right subtrees to the current node's value and 1, respectively.
   • Calculate the average of the current subtree.
   • Update the maximum average if the current average is greater.
   • Return the (sum, count) tuple for the current subtree.
3. Call the helper function on the root of the tree.
4. Return the maximum average found.

Edge Cases

• Empty tree (root is null): Return 0.0.
• Single node tree: Return the node's value as a double.

Code Example (Java)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private double maxAvg = Double.MIN_VALUE;

    public double maximumAverageSubtree(TreeNode root) {
        if (root == null) {
            return 0.0;
        }
        helper(root);
        return maxAvg;
    }

    private int[] helper(TreeNode node) {
        if (node == null) {
            return new int[] {0, 0};
        }

        int[] left = helper(node.left);
        int[] right = helper(node.right);

        int sum = left[0] + right[0] + node.val;
        int count = left[1] + right[1] + 1;

        double avg = (double) sum / count;
        maxAvg = Math.max(maxAvg, avg);

        return new int[] {sum, count};
    }
}

Big O Complexity

• Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node exactly once during the post-order traversal.
• Space Complexity: O(H), where H is the height of the tree. This is due to the recursion stack space used during the traversal. In the worst case (skewed tree), H can be N, resulting in O(N) space complexity. In the average case (balanced tree), H would be log(N), resulting in O(log(N)) space complexity.