> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/amazon-mock-interview/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/amazon-mock-interview/2022/oa/subtree-with-maximum-average.md).

# Subtree with Maximum Average

<https://leetcode.com/discuss/interview-question/349617#:~:text=Amazon%20%7C%20OA%202019%20%7C%20Subtree%20with%20Maximum%20Average,-88&text=A%20subtree%20of%20a%20tree,by%20the%20number%20of%20nodes.>\
&#x20;

Given an N-ary tree, find the subtree with the maximum average. Return the root of the subtree.\
A subtree of a tree is the node which have **at least 1 child** plus all its descendants. The average value of a subtree is the sum of its values, divided by the number of nodes.

**Example 1:**

```
Input:
            20
	   /   \
	 12     18
      /  |  \   / \
    11   2   3 15  8

Output: 18
Explanation:
There are 3 nodes which have children in this tree:
12 => (11 + 2 + 3 + 12) / 4 = 7
18 => (18 + 15 + 8) / 3 = 13.67
20 => (12 + 11 + 2 + 3 + 18 + 15 + 8 + 20) / 8 = 11.125

18 has the maximum average so output 18.
```

Similar questions:

* <https://leetcode.com/problems/maximum-average-subtree>\ <br>