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.)
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.
- The number of nodes in the tree is between
- Each node will have a value between
- Answers will be accepted as correct if they are within
10^-5of the correct answer.
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
- Count of the nodes in the
nodesubtree, let’s refer to it as
Then, the average for subtree rooted at
node will be
Now, to calculate these values for a subtree rooted at
node, we can derive them from the child nodes of
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
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 + right + node.val number_of_nodes = left + right + 1 max_average = max(left, right, curr_sum/(1+left+right)) return curr_sum, number_of_nodes, max_average return dfs(root)
- 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 .