Maximum Average Subtree

Problem Description

Given the root of a binary tree, find the maximum average value of any subtree of that tree.

Each node in the tree has a value. The average value of a subtree is defined as the sum of the values of all nodes in the subtree divided by the number of nodes in the subtree.

Naive Solution

A brute-force solution would involve traversing every node in the tree and considering it as the root of a subtree. For each subtree, calculate the sum of its nodes and the number of nodes. Then calculate the average. Keep track of the maximum average seen so far.

This approach is inefficient because calculating the sum and count for each subtree involves redundant calculations. For example, when considering a node's grandparent as the root, the sums and counts for the node and its sibling's subtrees are recalculated even though they were already computed when the node and sibling were considered as roots.

Optimal Solution

A more efficient approach involves a post-order traversal of the tree. During the traversal, for each node, we calculate:

1. The sum of the values of all nodes in its subtree (including the node itself).
2. The number of nodes in its subtree (including the node itself).

We can then calculate the average value of the subtree rooted at that node. We keep track of the maximum average encountered during the traversal.

This approach avoids redundant calculations by calculating the sum and count for each subtree only once. The post-order traversal ensures that the sums and counts for a node's children are calculated before calculating the sum and count for the node itself.

Edge Cases

• Empty Tree: If the root is null, return 0.
• Single Node Tree: If the root has no children, the maximum average is simply the root's value.
• Negative Values: The tree can contain nodes with negative values, which should be correctly factored into the average calculation.

Code (Python)

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def maximumAverageSubtree(self, root: TreeNode) -> float:
        max_avg = float('-inf')

        def postorder(node):
            nonlocal max_avg
            if not node:
                return 0, 0  # (sum, count)

            left_sum, left_count = postorder(node.left)
            right_sum, right_count = postorder(node.right)

            subtree_sum = node.val + left_sum + right_sum
            subtree_count = 1 + left_count + right_count

            avg = subtree_sum / subtree_count
            max_avg = max(max_avg, avg)

            return subtree_sum, subtree_count

        postorder(root)
        return max_avg

Time and Space 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 recursive call stack during the post-order traversal. In the worst case (skewed tree), H can be equal to N, resulting in O(N) space complexity. In the best case (balanced tree), H would be log(N), resulting in O(log N) space complexity.