Leetcode: Maximum Average Subtree

This question is asked at Amazon, Facebook, and Atlassian. 

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 off of its descendants, the average value of the tree is the sum of its values divided by the number of trees. 

The output is 6.000

For node is 5 we have (5 + 6 + 1) / 3 = (11 + 1) / 3 = (12) / 3 = 4.

For the node with a value = 1, we have an average of 1/1 = 1.

Node with value 6 we have 1/1 = 1, so the answer is 6 which is the maximum. 

We go through the values and get the maximum of the nodes. 

Every node is making a query from the results of the left child and the right child. 

So, we are making a query of recursive calls.

To calculate the average value, we need

1. The sum of all the values of the nodes in the subtree node, refer to it as ValueSum(node). 

2. Count of the nodes in the node subtree, let's refer to it as NodeCount(node). 

The average for the subtree rooted at node will be the ValueSum(node) / NodeCount(node). 

Now to calculate these values for a subtree rooted at a node, we can derive them from the child nodes of the node.

ValueSum(node) = ValueSum(node.left) + ValueSum(node.right) + Value(node)

NodeCount(node) = NodeCount(node.left) + NodeCount(node.right) + 1

For a leaf (no children) the ValueSum(leaf) = node.val and the NodeCount(leaf) = 1. We can calculate the average for each node in the tree and maximize the average after the post-order traversal. 

class Solution {

    class State {

        int nodeCount;

        int valueSum;

        double maxAverage;

        //initialize a state to be later referenced. 

        State(int nodes, int sum, double maxAverage) {

            this.nodeCount = nodes;

            this.valueSum = sum;

            this.maxAverage = maxAverage;

        }

        public double maximumAverageSubtree(TreeNode root) {

            return maxAverage(root).maxAverage;

        }

        State maxAverage(TreeNode root) { 

            //base case no children

            if(root == null) {

                return new State(0, 0, 0);

            }

            //recursive call

            State left = maxAverage(root.left);

            State right = maxAverage(root.right);

            //figure out the node count based on node recursively and sum and average

            int nodeCount = left.nodeCount + right.nodeCount + 1;

            int sum = left.valueSum + right.valueSum + root.val;

            double maxAverage = Math.max( (1.0 * (sum)) / nodeCount, Math.max(right.maxAverage, left.maxAverage) )

            //return new state that can bee referenced later. 

            return new State(nodeCount, sum, maxAverage);

    } 

}