# Subtree Max Avg

## Subtree with Minimum Sum ([LC.596](http://www.lintcode.com/en/problem/minimum-subtree/))

> 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

```java
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](http://www.lintcode.com/en/problem/subtree-with-maximum-average/))

> 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

```java
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);
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://zedive.gitbook.io/project-l/part-1/basic_data_structure/binary_tree/divide_and_conquer/subtree-w-minimum-sum.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.