Frontend School

Maximum Average Subtree Demand

DSA
medium

Maximum Average Subtree Demand

Medium
Tree
DFS
Traversal
Binary Tree

Overview

Uber's operations team continuously optimizes driver distribution and pricing strategies based on real-time demand. To identify key zones for intervention, they've modeled geographical areas as a hierarchical tree structure. Each node in this tree represents a specific zone and carries a numerical demand score. The goal is to pinpoint the most impactful areas by finding the subtree that exhibits the highest average demand score.

What you need to do / Task

Implement a function maxAverageSubtreeDemand that, given the root of a binary tree, identifies and returns the demand score (val) of the root node of the subtree with the highest average demand. The average demand of a subtree is calculated as the sum of demand values of all nodes within that subtree divided by the total number of nodes in that subtree.

Input & output

Input:

  • root: The root node of a binary tree. Each TreeNode has an integer val (representing demand), and left and right pointers to child TreeNodes or null.

Output:

  • number: The val of the root node of the subtree that has the maximum average demand. If the tree is empty, return 0. If multiple subtrees have the same maximum average demand, any corresponding node's val is acceptable.

Clarifications

  • Empty Tree: If the input root is null, return 0.
  • Node Values: Demand scores (val) can be positive, negative, or zero.
  • Average Calculation: Integer division is not desired. Use floating-point division for average calculation.
  • Single Node Tree: A single node is considered a subtree of itself. Its average demand is simply its val.

Examples

1

Example 1

Input:

root = [5,2,-3]

Output:

2

Note:

Subtree with root 2: sum=2, count=1, avg=2. Subtree with root -3: sum=-3, count=1, avg=-3. Subtree with root 5 (full tree): sum=5+2-3=4, count=3, avg=4/3≈1.33. The maximum average is 2, from the subtree rooted at node 2.

2

Example 2

Input:

root = [-1,-2,-3,-4,-5]

Output:

-3

Note:

Subtree with root -4: avg=-4. Subtree with root -5: avg=-5. Subtree with root -2 (nodes -2,-4,-5): sum=-11, count=3, avg≈-3.67. Subtree with root -3: avg=-3. Subtree with root -1 (full tree): sum=-15, count=5, avg=-3. The maximum average is -3, which occurs at node -1 and node -3. Returning -3 is acceptable.

3

Example 3

Input:

root = [10]

Output:

10

Note:

The only subtree is the root itself. Sum=10, count=1, average=10.

4

Example 4

Input:

root = []

Output:

0

Note:

An empty tree, as per clarifications, should return 0.

Constraints

Constraints & assumptions

  • The number of nodes in the tree will be in the range [0, 10^4].
  • -10^5 <= Node.val <= 10^5.
  • The tree structure is always valid (no cycles, no invalid pointers).

Out of scope

  • Handling non-numeric demand values or invalid tree structures.
  • Optimizing for memory beyond standard recursion stack limits (stack depth will be O(N) in worst case, O(log N) for balanced trees).
  • Returning the entire subtree or its root node object; only the val is required.

What interviewers evaluate

  • Correctness: The solution correctly identifies the subtree with the maximum average demand across all valid tree structures and edge cases.
  • Algorithm Design: The chosen tree traversal strategy (e.g., DFS/BFS) is appropriate and efficiently processes subtree information.
  • Code Quality: The code is well-structured, readable, and adheres to standard practices.
  • Edge Case Handling: The solution gracefully handles cases like an empty tree or a single-node tree.
  • Time & Space Complexity: The solution demonstrates an understanding of the time and space complexity, aiming for optimal performance (e.g., O(N) time).

Loading editor...