Problem Statement

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.00000Explanation: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:**

- The number of nodes in the tree is between
`1`

and`5000`

. - Each node will have a value between
`0`

and`100000`

. - 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:

- Sum of all values of the nodes in the subtree of
`node`

, let’s refer to it as`ValueSum(node)`

. - 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`

.

`ValueSum(node) = ValueSum(node.left) + ValueSum(node.right) + Value(node)`

`NodeCount(node) = NodeCount(node.left) + NodeCount(node.right) + 1`

Also, for any leaf node `leaf`

, we know that:

`ValueSum(leaf) = node.val`

`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.

You can read more about different binary tree traversals here.

# 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 .