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.

img

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 : O(N), where N 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 : O(N), because we will create N 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 N, hence space complexity from this will also be O(N).

Leave a reply