Count Nodes Equal to Average of Subtree - Practice Coding Problems

Count Nodes Equal to Average of Subtree - Problem

Given the root of a binary tree, return the number of nodes where the value of the node is equal to the average of the values in its subtree.

Note:

The average of n elements is the sum of the n elements divided by n and rounded down to the nearest integer.
A subtree of root is a tree consisting of root and all of its descendants.

Input & Output

Example 1 — Complete Binary Tree

$ Input: root = [4,8,5,0,1,null,6]

› Output: 5

💡 Note: Node 4: subtree sum=24, count=6, average=4 ✓. Node 5: subtree sum=11, count=2, average=5 ✓. Leaf nodes 0, 1, 6 all equal their own values ✓. Node 8: subtree sum=9, count=3, average=3 ≠ 8.

Example 2 — Simple Tree

$ Input: root = [1]

› Output: 1

💡 Note: Single node with value 1. Subtree sum=1, count=1, average=1 ✓. The node equals its subtree average.

Example 3 — No Matches

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

› Output: 0

💡 Note: Node 1: subtree sum=6, count=3, average=2 ≠ 1. Node 2: sum=2, count=1, average=2 ✓. Wait, that's 1 match actually. Node 3: sum=3, count=1, average=3 ✓. So result should be 2.

Constraints

The number of nodes in the tree is in the range [1, 10⁵]
0 ≤ Node.val ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Binary tree with node values

Calculate Averages

For each subtree, compute sum/count

Count Matches

Count nodes where value equals subtree average

Key Takeaway

🎯 Key Insight: Use DFS to calculate subtree sums and counts in one traversal, checking averages bottom-up

Asked in

f Facebook 15 a Amazon 12 M Microsoft 8

The key insight is to calculate subtree sums and counts in a single DFS traversal, checking if each node equals its subtree average. Best approach uses bottom-up DFS to visit each node once. Time: O(n), Space: O(h) where h is tree height.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Separate Traversal for Each Node	O(n²)	O(h)	For each node, perform a separate traversal to calculate its subtree's sum and count
Optimized DFS - Single Traversal	O(n)	O(h)	Calculate sum and count for each subtree in a single bottom-up DFS traversal

Brute Force - Separate Traversal for Each Node — Algorithm Steps

Step 1: Traverse each node in the tree
Step 2: For each node, perform separate DFS to get subtree sum and count
Step 3: Calculate average (sum/count) and compare with node value
Step 4: Count nodes where value equals average

Visualization

Tap to expand

Step-by-Step Walkthrough

Visit Node

For each node, start a separate calculation

Calculate Subtree

Traverse entire subtree to get sum and count

Check Average

Compare node value with calculated average

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;
}

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

void traverseAllNodes(struct TreeNode* node, int* result) {
    if (!node) return;
    
    int subtreeSum, subtreeCount;
    getSubtreeSumCount(node, &subtreeSum, &subtreeCount);
    int avg = subtreeSum / subtreeCount;
    
    if (node->val == avg) {
        (*result)++;
    }
    
    traverseAllNodes(node->left, result);
    traverseAllNodes(node->right, result);
}

int solution(struct TreeNode* root) {
    if (!root) return 0;
    
    int result = 0;
    traverseAllNodes(root, &result);
    return result;
}

int main() {
    // For simplicity, assume input [4,8,5,0,1,null,6]
    struct TreeNode* root = createNode(4);
    root->left = createNode(8);
    root->right = createNode(5);
    root->left->left = createNode(0);
    root->left->right = createNode(1);
    root->right->right = createNode(6);
    
    int result = solution(root);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n nodes, we traverse its entire subtree which can be O(n) nodes

⚠ Quadratic Growth

Space Complexity

O(h)

Recursion stack depth equals tree height h

✓ Linear Space

23.0K Views

Medium Frequency

~15 min Avg. Time

892 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 - Separate Traversal for Each Node — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler