Maximum Average Subtree

MediumTreestree dp

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Given the root of a non-empty binary tree, return the largest **average value** over all of its subtrees. A subtree is any node together with all of its descendants. Its average is the sum of its values divided by the number of nodes it contains. Answers within 1e-6 of the correct value are accepted.

Examples

Input: root = [5,6,1]
Output: 6.0
The subtree rooted at 5 averages 4, the leaf 6 averages 6, and the leaf 1 averages 1.
Input: root = [0,null,1]
Output: 1.0
The leaf 1 averages 1, which beats the root's average of 0.5.

Constraints

  • 1 <= number of nodes <= 10^4
  • 0 <= Node.val <= 10^5

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More tree dp problems