Leetcode 1120. Maximum Average Subtree

Problem Explanation:

This problem revolves around data structure of binary trees and can be solved through depth-first-search algorithm. Given a binary tree with each node carrying certain integer values, the task is to find maximum average value of any subtree of the provided tree. Here, a subtree is defined as one of the nodes of the tree along with all its descendants. The average value is computed as the sum of all the values divided by the number of nodes.

Take this tree for an example,

1    5
2   / \
3  6   1

Here, there are three sub-trees.
Subtree 1 is the entire tree where average=(5+6+1)/3=4
Subtree 2 consists only the left node with value=6; average=6/1=6
Subtree 3 consists only the right node with value=1; average=1/1=1
Out of these three averages, maximum is 6 belonging to subtree 2.

Approach:

A recursion-based approach using depth-first-search isfit to solve this problem. Starting with the root node of the tree, we will dive deeper into both left and right directions recursively to calculate sums and counts. As we emerge back after reaching the end of a particular path, we can compute the averages and at the same time, track maximum among these. Return this maximum as the final result.

Walk-through:

For our example tree, start at root node with value=5.

1    5
2   / \
3  6   1
4  

We dive into left direction and reach the node with value=6. As this is the end, we return the sum=6, count=1, and maxAverage=6 (since there is only one node). Next, we dive into right direction and reach the node with value=1. As this is the end, we return the sum=1, count=1 and maxAverage=1 (since there is only one node). Now we return back to the root and calculate the sum=5(root value)+6(left sum)+1(right sum)=12, the count is 1(root)+1(left count)+1(right count)=3 and the average is 12/3=4. We track the maximum among 4, 6 (left average) and 1 (right average) as 6.

Return this 6 as the maximum average of any subtree within the tree.

Let's see the actual codes written in several languages for this approach:

Python Solution:

1
2python
3class Solution:
4    def maximumAverageSubtree(self, root):
5        def dfs(node):
6            if not node: return 0.0, 0, 0.0
7            l_sum, l_count, l_max = dfs(node.left)
8            r_sum, r_count, r_max = dfs(node.right)
9            cur_sum = l_sum + r_sum + node.val
10            cur_count = l_count + r_count + 1
11            return cur_sum, cur_count, max(l_max, r_max, cur_sum / cur_count)
12        return dfs(root)[2]

Java Solution:

1
2java
3class Solution {
4    public double maximumAverageSubtree(TreeNode root) {
5        return maximumAverage(root).maxAverage;
6    }
7
8    private T maximumAverage(TreeNode root) {
9        if (root == null)
10            return new T(0, 0, 0.0);
11
12        T left = maximumAverage(root.left);
13        T right = maximumAverage(root.right);
14
15        int sum = root.val + left.sum + right.sum;
16        int count = 1 + left.count + right.count;
17        double maxAverage = Math.max(sum / (double)count, Math.max(left.maxAverage, right.maxAverage));
18        return new T(sum, count, maxAverage);
19    }
20}

JavaScript Solution:

1
2javascript
3var maximumAverageSubtree = function(root) {
4    let max = -Infinity;
5    function dfs(root) {
6        if(!root) return [0,0];
7        let [lsum,lsize] = dfs(root.left);
8        let [rsum,rsize] = dfs(root.right);
9        max = Math.max(max,(root.val+lsum+rsum)/(1+lsize+rsize));
10        return [root.val+lsum+rsum,1+lsize+rsize]
11    }
12    dfs(root);
13    return max;
14};

C++ Solution:

1
2cpp
3class Solution {
4public:
5    double maximumAverageSubtree(TreeNode* root) {
6        helper(root);
7        return res;
8    }
9    
10    pair<int, int> helper(TreeNode* root) {
11        if(!root) return {0,0};
12        auto left = helper(root->left), right = helper(root->right);
13        int sum = left.first + right.first + root->val;
14        int num = left.second + right.second + 1;
15        res = max(res, static_cast<double>(sum) / num);
16        return {sum, num};
17    }
18private:
19    double res = 0;
20};

C# Solution:

1
2csharp
3public class Solution {
4    double maxAvg = 0.0;
5    public double MaximumAverageSubtree(TreeNode root) {
6        Avg(root);
7        return maxAvg;
8    }
9    
10    public (double, int) Avg(TreeNode node)
11    {
12        if(node == null) return (0.0,0);
13        var left = Avg(node.left);
14        var right = Avg(node.right); 
15        var sum = left.Item1 + right.Item1 + node.val;
16        var count = left.Item2 + right.Item2 + 1;
17        maxAvg = Math.Max(maxAvg, sum/count);        
18        return (sum, count);  
19    }    
20}

Swift Solution:

1
2swift
3class Solution {
4    var result = 0.0
5    func maximumAverageSubtree(_ root: TreeNode?) -> Double {
6        dfs(root)
7        return result 
8    }
9    func dfs(_ root: TreeNode?) -> (Double,Int) { 
10        guard let root = root else {return (0,0)}
11        let left = dfs(root.left)
12        let right = dfs(root.right)
13        let sum = left.0 + right.0 + Double(root.val)
14        let count = left.1 + right.1 + 1
15        let avg = sum/Double(count)
16        result = max(result,avg)
17        return (sum, count)
18    }
19}

Ruby Solution:

1
2ruby
3class Solution
4  def maximum_average_subtree(root)
5    @max_avg = -1.0 / 0.0
6    calc_subtree(root)
7    @max_avg
8  end
9
10  private
11
12  def calc_subtree(node)
13    return [0, 0] if node.nil?
14    
15    left_sum, left_count = calc_subtree(node.left)
16    right_sum, right_count = calc_subtree(node.right)
17    sum = left_sum + node.val + right_sum
18    count = left_count + 1 + right_count
19    avg = sum.to_f / count
20    @max_avg = [avg, @max_avg].max
21    [sum, count]
22  end
23end

In all of the solutions above, each solution starts the traversal from the root node using the depth-first search algorithm. For each node, the sum and count of nodes in the substree rooted at the current node are computed recursively. The average is then calculated as the sum divided by the count and the maximum average is updated if the current average exceeds the previously recorded maximum average.

The time complexity is O(n), where n represents the number of nodes in the binary tree. For each node in the binary tree, its value, the sum of the values of its left subtree, and the sum of its right subtree are computed. This requires visiting each node exactly once, hence the time complexity is O(n). The space complexity is O(h), where h represents the height of the tree. This is because in the worst-case scenario, the maximum depth of the recursion stack would be the height of the binary tree.