Find Subtree with Maximum Average

To solve the 'Find Subtree with Maximum Average' problem efficiently, I would use a post-order depth-first search approach. The core insight is that we cannot calculate the average of a subtree without knowing the sum of all its descendants and the total number of nodes. Instead of traversing the tree multiple times, which would lead to O(N^2) complexity, we can compute these metrics in a single pass. I will implement a recursive helper function that returns an array or object containing two values: the sum of the subtree and the count of nodes within it. For each node, the function first recursively processes the left and right children. Once those return, I add their sums together and add their counts together, then include the current node's value and count of one. With these aggregated values, I calculate the current subtree's average as sum divided by count. I compare this against a running maximum average initialized to negative infinity. If the current average is higher, I update the global maximum. This ensures we capture the best subtree found so far. Finally, the main function returns the highest average found. This approach guarantees O(N) time complexity because we visit each node exactly once, and O(H) space complexity for the recursion stack, which aligns well with Meta's expectation for optimized, scalable solutions.