Subtree with Maximum Average

Given a binary tree root, return the maximum average value of a subtree. A subtree is defined to be some node in root including all of its descendants. A subtree average is the sum of the node values divided by the number of nodes.

Constraints

• 1 ≤ n ≤ 100,000 where n is the number of nodes in root

https://binarysearch.com/problems/Subtree-with-Maximum-Average

Examples

Example 1

Input

• root =

Output

• answer = 5.5

Explanation

The subtree rooted at 7 has the highest average with (7 + 4) / 2.

Example 2

Input

• root =

Output

• answer = 4

Explanation

The subtree rooted at 4 has the highest average with 4 / 1.

Solution