Teaching Kids Programming – Recursive Depth First Search Algorithm to Compute the Max Average of a Binary SubTree

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given the root of a binary tree, return the maximum average value of a subtree of that tree. Answers within 10-5 of the actual answer will be accepted. 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: root = [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.

Example 2:
Input: root = [0,null,1]
Output: 1.00000

Constraints:
The number of nodes in the tree is in the range [1, 104].
0 <= Node.val <= 10^5

Hints:
Can you find the sum of values and the number of nodes for every sub-tree ?
Can you find the sum of values and the number of nodes for a sub-tree given the sum of values and the number of nodes of it’s left and right sub-trees ?
Use depth first search to recursively find the solution for the children of a node then use their solutions to compute the current node’s solution.

Recursive Depth First Search Algorithm to Compute the Max Average of a Binary SubTree

Based on the Recursive Function to compute the sum of a binary tree, we can let it also return the number of the nodes. We can use a tuple (immutable list) or list to store both sum and number of nodes. Then we can compute the average and store the maxmimum value of it.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# 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: Optional[TreeNode]) -> float:
        ans = 0        
 
        def dfs(root):
            if not root:
                return (0, 0)
            nonlocal ans
            left, cnt1 = dfs(root.left)
            right, cnt2 = dfs(root.right)
            c = cnt1 + cnt2 + 1
            s = left + right + root.val
            ans = max(ans, s / c)
            return (s, c)
 
        dfs(root)
        return ans

# 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: Optional[TreeNode]) -> float:
        ans = 0        

        def dfs(root):
            if not root:
                return (0, 0)
            nonlocal ans
            left, cnt1 = dfs(root.left)
            right, cnt2 = dfs(root.right)
            c = cnt1 + cnt2 + 1
            s = left + right + root.val
            ans = max(ans, s / c)
            return (s, c)

        dfs(root)
        return ans

The time and space complexity is O(N) where N is the number of the nodes in the given binary tree.

See also: The Maximum Average Subtree of a Binary Tree

–EOF (The Ultimate Computing & Technology Blog) —