## Similar Problems

Similar Problems not available

# Maximum Average Subtree - Leetcode Solution

## Companies:

LeetCode: Maximum Average Subtree Leetcode Solution

Difficulty: Medium

Topics: tree binary-tree depth-first-search

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.

## Maximum Average Subtree Solution Code

`1`