Average of Levels in Binary Tree - Practice Coding Problems

Average of Levels in Binary Tree - Problem

Given the root of a binary tree, return the average value of the nodes on each level in the form of an array.

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

Input & Output

Example 1 — Basic Tree

$ Input: root = [3,9,20,null,null,15,7]

› Output: [3.0,14.5,11.0]

💡 Note: Level 0: node 3 → average = 3.0. Level 1: nodes 9,20 → average = (9+20)/2 = 14.5. Level 2: nodes 15,7 → average = (15+7)/2 = 11.0

Example 2 — Single Node

$ Input: root = [1]

› Output: [1.0]

💡 Note: Only one level with single node 1, so average is 1.0

Example 3 — Left-Heavy Tree

$ Input: root = [3,9,20,15,7]

› Output: [3.0,14.5,11.0]

💡 Note: Level 0: node 3 → 3.0. Level 1: nodes 9,20 → 14.5. Level 2: nodes 15,7 → 11.0

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Binary tree with nodes arranged in levels

Level Grouping

Group nodes by their depth level

Average Calculation

Compute average for each level

Key Takeaway

🎯 Key Insight: Use BFS to process complete levels at once for efficient average calculation

Asked in

A Amazon 35 F Facebook 22 L LinkedIn 18 M Microsoft 15

The key insight is to process the tree level by level using BFS (breadth-first search). For each level, calculate the sum of all node values and divide by the count to get the average. Best approach is BFS with queue for O(1) space per level. Time: O(n), Space: O(w) where w is maximum tree width.

Common Approaches

Approach	Time	Space	Notes
✓ Level-Order BFS	O(n)	O(w)	Use breadth-first search to process nodes level by level and calculate averages immediately
DFS with Level Tracking	O(n)	O(n)	Use depth-first search to collect all nodes at each level, then calculate averages

Level-Order BFS — Algorithm Steps

Step 1: Use queue to process nodes level by level
Step 2: For each level, sum all node values and count nodes
Step 3: Calculate average immediately for each level

Visualization

Tap to expand

Step-by-Step Walkthrough

Queue Setup

Initialize queue with root node

Level Processing

Process all nodes at current level, add children to queue

Calculate Average

Compute average for each completed level

Code -

solution.c — C

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

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

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

double* solution(struct TreeNode* root, int* returnSize) {
    if (!root) {
        *returnSize = 0;
        return NULL;
    }
    
    double* result = (double*)malloc(1000 * sizeof(double));
    struct TreeNode* queue[10000];
    int front = 0, rear = 0;
    int resultSize = 0;
    
    queue[rear++] = root;
    
    while (front < rear) {
        int levelSize = rear - front;
        double levelSum = 0;
        int currentRear = rear;
        
        for (int i = front; i < currentRear; i++) {
            struct TreeNode* node = queue[i];
            levelSum += node->val;
            
            if (node->left) queue[rear++] = node->left;
            if (node->right) queue[rear++] = node->right;
        }
        
        result[resultSize++] = levelSum / levelSize;
        front = currentRear;
    }
    
    *returnSize = resultSize;
    return result;
}

struct TreeNode* buildSimpleTree() {
    struct TreeNode* root = createNode(3);
    root->left = createNode(9);
    root->right = createNode(20);
    root->right->left = createNode(15);
    root->right->right = createNode(7);
    return root;
}

int main() {
    char input[10000];
    fgets(input, sizeof(input), stdin);
    
    struct TreeNode* root = buildSimpleTree();
    int returnSize;
    double* result = solution(root, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%f", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Visit each node exactly once during BFS traversal

✓ Linear Growth

Space Complexity

O(w)

Queue stores at most w nodes where w is maximum width of tree

✓ Linear Space

185.0K Views

Medium Frequency

~15 min Avg. Time

2.9K 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

Level-Order BFS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler