Subtree Max Avg

Subtree with Minimum Sum (LC.596)

Given a binary tree, find the subtree with minimum sum. Return the root of the subtree.

Example

+    1
   /   \
 -5     2
 / \   /  \
0   2 -4  -5

root 1 has the minSubtree.

Analysis

Divide and conquer does not work well for this kind of problem. You need to somehow traverse it. (need a global value).

Code

private TreeNode minSubtree = null;
private int minSum = Integer.MAX_VALUE;
/**
 * @param root the root of binary tree
 * @return the root of the minimum subtree
 */
public TreeNode findSubtree(TreeNode root) {
    subtreeSum(root);
    return minSubtree;
}
private int subtreeSum(TreeNode root) {
    // base case
    if (root == null) {
        return 0;
    }
    // divide & conquer
    int currentSum = root.val + subtreeSum(root.left) + subtreeSum(root.right);
    // update global value
    if (currentSum < minSum) {
        minSum = currentSum;
        minSubtree = root;
    }
    return currentSum;
}

Subtree with Maximum Average (LC.597)

Given a binary tree, find the subtree with maximum average. Return the root of the subtree.

Example

+    1
   /   \
 -5     11
 / \   /  \
1   2 4    -2

Root 11's subtree.

Analysis

Again we need D&C with a global value. What's the return type for D&C and what to keep track as a global value?

Code

double maxAvg = Integer.MIN_VALUE;
TreeNode maxNode = null;

private class ReturnType {
    double sum;
    double numNodes;

    public ReturnType(double sum, double numNodes) {
        this.sum = sum;
        this.numNodes = numNodes;
    }
}

public TreeNode findSubtree2(TreeNode root) {
    avgSubtree(root);
    return maxNode;
}

private ReturnType avgSubtree(TreeNode root) {
    if (root == null) {
        return new ReturnType(0, 0);
    }    
    ReturnType leftSubtree = avgSubtree(root.left);
    ReturnType rightSubtree = avgSubtree(root.right);
    double currentSum = leftSubtree.sum + root.val + rightSubtree.sum;
    double currentNodes = leftSubtree.numNodes + 1 + rightSubtree.numNodes;
    double currentAvg = currentSum / currentNodes;
    if (currentAvg > maxAvg) {
        maxAvg = currentAvg;
        maxNode = root;
    }
    return new ReturnType(currentSum, currentNodes);
}