Given the `root` of a binary tree, find the maximum average value of any 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 the sum of its values, divided by the number of nodes.)

Example 1:

```Input: [5,6,1]
Output: 6.00000
Explanation:
For the node with value = 5 we have an average of (5 + 6 + 1) / 3 = 4.
For the node with value = 6 we have an average of 6 / 1 = 6.
For the node with value = 1 we have an average of 1 / 1 = 1.
So the answer is 6 which is the maximum.
```

Note:

1. The number of nodes in the tree is between `1` and `5000`.
2. Each node will have a value between `0` and `100000`.
3. Answers will be accepted as correct if they are within `10^-5` of the correct answer.

Solution

Approach 1: Postorder Traversal

Intuition and Algorithm

To calculate average value of a subtree rooted at `node`, we need two things:

1. Sum of all values of the nodes in the subtree of `node`, let’s refer to it as `ValueSum(node)`.
2. Count of the nodes in the `node` subtree, let’s refer to it as `NodeCount(node)`.

Then, the average for subtree rooted at `node` will be `ValueSum(node)/NodeCount(node)`.

Now, to calculate these values for a subtree rooted at `node`, we can derive them from the child nodes of `node`.

1. `ValueSum(node) = ValueSum(node.left) + ValueSum(node.right) + Value(node)`
2. `NodeCount(node) = NodeCount(node.left) + NodeCount(node.right) + 1`

Also, for any leaf node `leaf`, we know that:

1. `ValueSum(leaf) = node.val`
2. `NodeCount(leaf) = 1`

Looking at these equations, we can see that we can calculate average for each of the node in the tree by traversing bottom up i.e. first visit and calculate `ValueSum` and `NodeCount` for child nodes and then use these child nodes values to solve for parent node. This order of tree traversal is popularly known as postorder traversal.

```# 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
class Solution:
def maximumAverageSubtree(self, root: TreeNode) -> float:

#current sum, number of nodes, max average

def dfs(node):
if not node:
return 0, 0, 0
left = dfs(node.left)
right = dfs(node.right)
curr_sum = left[0] + right[0] + node.val
number_of_nodes = left[1] + right[1] + 1
max_average = max(left[2], right[2], curr_sum/(1+left[1]+right[1]))
return curr_sum, number_of_nodes, max_average
return dfs(root)[2]
```

Complexity Analysis

• Time complexity : , where  is the number of nodes in the tree. This is because we visit each and every node only once, as we do in postorder traversal.
• Space complexity : , because we will create  states for each of the nodes in the tree. Also, in cases where we have a skewed tree, we will implicitly maintain a recursion stack of size , hence space complexity from this will also be .

Previous Post

Next article