Maximum Average Subtree - Practice Coding Problems

Maximum Average Subtree - Problem

Given the root of a binary tree, return the maximum average value of a subtree of that tree.

Answers within 10^-5 of the actual answer will be accepted.

A subtree of a tree is any node of that tree plus all its descendants. The average value of a tree is the sum of its values, divided by the number of nodes.

Input & Output

Example 1 — Basic Tree

$ Input: root = [5,6,1]

› Output: 6.0

💡 Note: Tree has subtrees: node 5 (avg=4.0), node 6 (avg=6.0), node 1 (avg=1.0). Maximum is 6.0 from the single node 6.

Example 2 — Single Node

$ Input: root = [1]

› Output: 1.0

💡 Note: Only one subtree exists: the root node itself with value 1, so average is 1.0.

Example 3 — Larger Tree

$ Input: root = [1,null,2,null,3]

› Output: 3.0

💡 Note: Right-skewed tree. Node 3 has average 3.0, node 2 has average 2.5, root has average 2.0. Maximum is 3.0.

Constraints

The number of nodes in the tree is in the range [1, 10⁴]
-10⁴ ≤ Node.val ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Binary tree with node values

Calculate Averages

Find average for each possible subtree

Return Maximum

Return the highest average found

Key Takeaway

🎯 Key Insight: Use post-order DFS to calculate subtree statistics efficiently in one pass

Asked in

G Google 15 a Amazon 12 M Microsoft 8 F Facebook 6

The key insight is using post-order DFS traversal to calculate subtree statistics in a single pass. Best approach is the optimized DFS that visits each node once and computes sum, count, and maximum average efficiently. Time: O(n), Space: O(h)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Multiple DFS	O(n²)	O(h)	For each node, perform separate DFS to calculate subtree sum and count
Optimized DFS - Single Pass	O(n)	O(h)	Single post-order DFS that calculates subtree sum, count, and maximum average

Brute Force - Multiple DFS — Algorithm Steps

Step 1: Traverse each node in the tree
Step 2: For each node, perform DFS to get subtree sum and count
Step 3: Calculate average and update maximum

Visualization

Tap to expand

Step-by-Step Walkthrough

Visit Each Node

Traverse tree to get all nodes

Calculate Subtree

For each node, DFS to get sum and count

Track Maximum

Compare averages and keep maximum

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <float.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* createNode(int val) {
    struct TreeNode* node = malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

void getAllNodes(struct TreeNode* node, struct TreeNode** nodes, int* count) {
    if (!node) return;
    nodes[(*count)++] = node;
    getAllNodes(node->left, nodes, count);
    getAllNodes(node->right, nodes, count);
}

void getSubtreeSumCount(struct TreeNode* node, int* sum, int* count) {
    if (!node) {
        *sum = 0;
        *count = 0;
        return;
    }
    
    int leftSum, leftCount, rightSum, rightCount;
    getSubtreeSumCount(node->left, &leftSum, &leftCount);
    getSubtreeSumCount(node->right, &rightSum, &rightCount);
    
    *sum = node->val + leftSum + rightSum;
    *count = 1 + leftCount + rightCount;
}

double solution(struct TreeNode* root) {
    if (!root) return 0.0;
    
    double maxAvg = -DBL_MAX;
    struct TreeNode* nodes[1000];
    int nodeCount = 0;
    
    getAllNodes(root, nodes, &nodeCount);
    
    for (int i = 0; i < nodeCount; i++) {
        int subtreeSum, subtreeCount;
        getSubtreeSumCount(nodes[i], &subtreeSum, &subtreeCount);
        double avg = (double)subtreeSum / subtreeCount;
        if (avg > maxAvg) {
            maxAvg = avg;
        }
    }
    
    return maxAvg;
}

struct TreeNode* buildTree(int* arr, int size) {
    if (size == 0) return NULL;
    
    struct TreeNode* root = createNode(arr[0]);
    struct TreeNode* queue[1000];
    int front = 0, rear = 0;
    queue[rear++] = root;
    int i = 1;
    
    while (front < rear && i < size) {
        struct TreeNode* node = queue[front++];
        if (i < size && arr[i] != -1001) {
            node->left = createNode(arr[i]);
            queue[rear++] = node->left;
        }
        i++;
        if (i < size && arr[i] != -1001) {
            node->right = createNode(arr[i]);
            queue[rear++] = node->right;
        }
        i++;
    }
    
    return root;
}

int main() {
    int arr[1000];
    int size = 0;
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    char* token = strtok(line, "[],\n ");
    while (token != NULL) {
        if (strcmp(token, "null") == 0) {
            arr[size++] = -1001;
        } else {
            arr[size++] = atoi(token);
        }
        token = strtok(NULL, "[],\n ");
    }
    
    struct TreeNode* root = buildTree(arr, size);
    double result = solution(root);
    printf("%f\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n nodes, we perform O(n) DFS to calculate subtree statistics

⚠ Quadratic Growth

Space Complexity

O(h)

Recursion stack depth is tree height h

✓ Linear Space

32.0K Views

Medium Frequency

~15 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Multiple DFS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler