LeetCode 1120 - Maximum Average Subtree

This problem asks us to find the maximum average value among all subtrees of a given binary tree. A subtree is defined as any node along with all of its descendants. The average of a subtree is the sum of its node values divided by the number of nodes in that subtree.

leetcodemediumtreedepth-first-searchbinary-tree

LeetCode Problem 1120

Difficulty: 🟡 Medium
Topics: Tree, Depth-First Search, Binary Tree

Solution

Problem Understanding

This problem asks us to find the maximum average value among all subtrees of a given binary tree. A subtree is defined as any node along with all of its descendants. The average of a subtree is the sum of its node values divided by the number of nodes in that subtree.

The input is the root node of a binary tree. Each node contains an integer value, and the tree may have up to 10,000 nodes. Node values range from 0 to 10^5. The expected output is a floating-point number representing the maximum average value among all possible subtrees. Answers are considered correct if they are within 10^-5 of the actual maximum average.

Important edge cases include trees with only one node, trees with all nodes having the same value, or highly unbalanced trees. The constraints ensure that every tree has at least one node and that the number of nodes is moderate enough to allow a depth-first traversal solution.

Approaches

The brute-force approach involves computing the sum and number of nodes for every possible subtree separately. For each node, we would recursively calculate the sum and count for its subtree, compute the average, and keep track of the maximum. While correct, this approach is inefficient because it recomputes subtree sums multiple times. For a tree with n nodes, this can lead to O(n^2) time complexity in the worst case, which is unacceptable for n = 10^4.

The optimal approach uses a bottom-up depth-first search (DFS). By performing a post-order traversal, we can calculate the sum and count of nodes for each subtree exactly once. At each node, we compute the subtree sum and size by combining the results from the left and right children, calculate the average, and update the global maximum if needed. This ensures every node is visited only once, yielding an O(n) time complexity.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(h) Recursively compute sum and count for each subtree separately; recomputation is expensive
Optimal O(n) O(h) DFS post-order traversal; compute sum and count once per node; h is tree height

Algorithm Walkthrough

  1. Initialize a global variable to track the maximum average found so far.
  2. Define a recursive helper function that accepts a node and returns a tuple (subtree_sum, subtree_count).
  3. If the node is None, return (0, 0) since an empty subtree contributes no sum or nodes.
  4. Recursively call the helper function on the left and right children to obtain their sums and counts.
  5. Compute the total sum for the current subtree as the sum of the node's value plus left and right subtree sums.
  6. Compute the total count of nodes in the current subtree as 1 + left_count + right_count.
  7. Calculate the average for the current subtree as total_sum / total_count.
  8. Update the global maximum average if the current average is larger.
  9. Return (total_sum, total_count) to the parent call.
  10. Finally, after traversing the entire tree, return the maximum average.

Why it works: This approach ensures that each subtree’s sum and size are computed exactly once. By propagating these values up from the leaves to the root, we avoid redundant calculations while correctly considering every subtree for the maximum average.

Python Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from typing import Optional

class Solution:
    def maximumAverageSubtree(self, root: Optional[TreeNode]) -> float:
        self.max_avg = float('-inf')
        
        def dfs(node: Optional[TreeNode]) -> tuple[int, int]:
            if not node:
                return (0, 0)
            left_sum, left_count = dfs(node.left)
            right_sum, right_count = dfs(node.right)
            
            total_sum = node.val + left_sum + right_sum
            total_count = 1 + left_count + right_count
            current_avg = total_sum / total_count
            
            self.max_avg = max(self.max_avg, current_avg)
            
            return (total_sum, total_count)
        
        dfs(root)
        return self.max_avg

The Python solution uses a recursive DFS. The helper dfs returns both the sum and count of the subtree rooted at each node. The maximum average is updated during the post-order traversal. Using a tuple avoids recomputation and keeps the code concise.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maximumAverageSubtree(root *TreeNode) float64 {
    var maxAvg float64 = -1
    var dfs func(node *TreeNode) (int, int)
    
    dfs = func(node *TreeNode) (int, int) {
        if node == nil {
            return 0, 0
        }
        leftSum, leftCount := dfs(node.Left)
        rightSum, rightCount := dfs(node.Right)
        
        totalSum := node.Val + leftSum + rightSum
        totalCount := 1 + leftCount + rightCount
        currentAvg := float64(totalSum) / float64(totalCount)
        
        if currentAvg > maxAvg {
            maxAvg = currentAvg
        }
        return totalSum, totalCount
    }
    
    dfs(root)
    return maxAvg
}

The Go solution mirrors the Python approach, using a recursive DFS function. In Go, care is taken to convert integers to float64 for average calculation. The nil check replaces Python’s None.

Worked Examples

Example 1: [5,6,1]

Node Left Sum Left Count Right Sum Right Count Total Sum Total Count Average Max Avg
6 0 0 0 0 6 1 6.0 6.0
1 0 0 0 0 1 1 1.0 6.0
5 6 1 1 1 12 3 4.0 6.0

Maximum average is 6.0.

Example 2: [0,null,1]

Node Left Sum Left Count Right Sum Right Count Total Sum Total Count Average Max Avg
1 0 0 0 0 1 1 1.0 1.0
0 0 0 1 1 1 2 0.5 1.0

Maximum average is 1.0.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each node is visited exactly once in the DFS traversal
Space O(h) Recursion stack for a tree of height h; worst-case O(n) for skewed tree

The algorithm is efficient because it avoids redundant calculations and traverses the tree only once. Space usage is proportional to the recursion depth.

Test Cases

# test cases
root1 = TreeNode(5, TreeNode(6), TreeNode(1))
assert abs(Solution().maximumAverageSubtree(root1) - 6.0) < 1e-5  # Example 1

root2 = TreeNode(0, None, TreeNode(1))
assert abs(Solution().maximumAverageSubtree(root2) - 1.0) < 1e-5  # Example 2

root3 = TreeNode(1)
assert abs(Solution().maximumAverageSubtree(root3) - 1.0) < 1e-5  # Single node

root4 = TreeNode(1, TreeNode(1), TreeNode(1))
assert abs(Solution().maximumAverageSubtree(root4) - 1.0) < 1e-5  # All same values

root5 = TreeNode(1, TreeNode(2, TreeNode(3, TreeNode(4))), None)
assert abs(Solution().maximumAverageSubtree(root5) - 4.0) < 1e-5  # Skewed tree
Test Why
[5,6,1] Normal small tree with varied values
[0,null,1] Tree with missing left child
[1] Single-node tree
[1,1,1] Uniform values
Skewed [1,2,3,4] Deep left-skewed tree to check recursion

Edge Cases

Single Node Tree: When the tree has only one node, the maximum average is simply the value of that node. The implementation handles this naturally because the DFS base case returns (0,0) for null children.

Uniform Values: If all nodes have the same value, any subtree has the same average. The maximum