Maximum Average Subtree - Leetcode Solution

The problem statement for the Maximum Average Subtree problem on leetcode is as follows:

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

In order to solve this problem, we need to traverse the binary tree and calculate the average of each subtree. We can do this recursively starting from the root node. At each node, we can calculate the average of the left and right subtree and compare it with the current maximum average subtree. We can keep track of the maximum average subtree found so far and return it at the end.

Here is the detailed solution for the Maximum Average Subtree problem:

Step 1: Define the function

Start by defining a recursive function that takes the root of the binary tree as an argument.

def maximumAverageSubtree(root):
    pass

Step 2: Initialize variables

Initialize variables to keep track of the maximum average subtree found so far and the number of nodes in that subtree.

    max_average = 0
    max_node_count = 0

Step 3: Define the recursive function

The recursive function should return the total sum and the number of nodes for each subtree. For each subtree, we can calculate the average value and compare it with the current maximum average.

def dfs(node):
    nonlocal max_average, max_node_count
    if not node:
        return 0, 0
    left_sum, left_count = dfs(node.left)
    right_sum, right_count = dfs(node.right)
    total_sum = left_sum + right_sum + node.val
    total_count = left_count + right_count + 1
    average = total_sum / total_count
    if average > max_average:
        max_average = average
        max_node_count = total_count
    return total_sum, total_count

Step 4: Call the recursive function

Call the recursive function with the root node as the starting argument.

dfs(root)

Step 5: Return the maximum average and the size of that subtree

return max_node_count

The final solution code looks like this:

def maximumAverageSubtree(root):
    max_average = 0
    max_node_count = 0

    def dfs(node):
        nonlocal max_average, max_node_count
        if not node:
            return 0, 0
        left_sum, left_count = dfs(node.left)
        right_sum, right_count = dfs(node.right)
        total_sum = left_sum + right_sum + node.val
        total_count = left_count + right_count + 1
        average = total_sum / total_count
        if average > max_average:
            max_average = average
            max_node_count = total_count
        return total_sum, total_count

    dfs(root)

    return max_node_count

This solution has a time complexity of O(n) and a space complexity of O(h), where n is the number of nodes in the binary tree and h is the height of the binary tree.

1