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:

  5
 / \
6   1

Input: [5,6,1]
Output: 6.00000

Explanation:

• For the node with value = 5 we have and average of (5 + 6 + 1) / 3 = 4.
• For the node with value = 6 we have and average of 6 / 1 = 6.
• For the node with value = 1 we have and 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.

Depth First Search Algorithm to Compute the Maximum SubTree Average

Similar problem: How to Find out the Most Frequent Subtree Sum using Depth First Search Algorithm?

To compute the average, we need the sum and as well as the number of nodes. We use the second parameter (reference) to pass down the counter. And the Depth First Search function will return the sum for the subtree. As we compute the average, we can record the maximum.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    double maximumAverageSubtree(TreeNode* root) {
        int cnt = 0;
        getSum(root, cnt);
        return maxAvg;
    }
    
private:
    int getSum(TreeNode* root, int &cnt) {
        if (root == nullptr) return 0;
        int left_cnt = 0;
        int right_cnt = 0;
        int left = getSum(root->left, left_cnt);
        int right = getSum(root->right, right_cnt);
        int sum = left + right + root->val;
        cnt = left_cnt + right_cnt + 1;
        maxAvg = max(maxAvg, (double)sum / cnt);
        return sum;
    }
    double maxAvg = 0.0;
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    double maximumAverageSubtree(TreeNode* root) {
        int cnt = 0;
        getSum(root, cnt);
        return maxAvg;
    }
    
private:
    int getSum(TreeNode* root, int &cnt) {
        if (root == nullptr) return 0;
        int left_cnt = 0;
        int right_cnt = 0;
        int left = getSum(root->left, left_cnt);
        int right = getSum(root->right, right_cnt);
        int sum = left + right + root->val;
        cnt = left_cnt + right_cnt + 1;
        maxAvg = max(maxAvg, (double)sum / cnt);
        return sum;
    }
    double maxAvg = 0.0;
};

The time and space complexity is O(N) as we are using recursion (implicitly using stacks) to conduct the Depth First Search. The N is the number of the nodes in the tree, which could be degerated to a linked list.

–EOF (The Ultimate Computing & Technology Blog) —