We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Average Subtree

Number: 1091

Difficulty: Medium

Paid? Yes

Companies: Amazon

Problem Description

Given the root of a binary tree, return the maximum average value of a subtree of that tree. A subtree of a tree is any node of that tree plus all its descendants. The average value of a tree is defined as the sum of its values divided by the number of nodes. Answers within 10⁻⁵ of the actual answer will be accepted.

Key Insights

  • Use a depth-first search (DFS) to traverse every subtree.
  • At each node, compute the sum and count of nodes in its subtree.
  • Calculate the average for the current subtree and update a global maximum if needed.
  • Processing every node exactly once yields an efficient solution.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes (each node is visited once).
Space Complexity: O(h), where h is the height of the tree (space for recursion stack).

Solution

We perform a post-order DFS traversal, calculating at each node both the cumulative sum and the count of nodes in its subtree. This enables us to compute the average value in constant time for any subtree. We maintain a global variable to track the maximum average encountered during the traversal. The primary technique is recursive DFS combined with tuple (or pair) aggregation. The simplicity of the recursion and in-place aggregation ensures an efficient and clear solution.

Code Solutions

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val        # value of the node
        self.left = left      # left child
        self.right = right    # right child

class Solution:
    def maximumAverageSubtree(self, root):
        # Initialize the maximum average to negative infinity
        self.maxAvg = float('-inf')
        
        # Recursive DFS function that returns a tuple (subtree sum, node count)
        def dfs(node):
            if not node:
                return (0, 0)  # return sum 0 and count 0 if node is null
            leftSum, leftCount = dfs(node.left)   # traverse left subtree
            rightSum, rightCount = dfs(node.right)  # traverse right subtree
            currentSum = node.val + leftSum + rightSum   # total sum at current node
            currentCount = 1 + leftCount + rightCount      # total node count
            currentAvg = currentSum / currentCount         # average value for current subtree
            self.maxAvg = max(self.maxAvg, currentAvg)      # update maximum average if necessary
            return (currentSum, currentCount)
        
        dfs(root)
        return self.maxAvg
← Back to All Questions