Count Nodes Equal to Average of Subtree — Problem & Solution
Count Nodes Equal to Average of Subtree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Count Nodes Equal to Average of Subtree is a medium coding problem on depth-first search and trees, asked in Amazon, Google and Meta interviews.
- Difficulty: Medium
- Topics: Depth-First Search, Trees
- Asked at: Amazon, Google, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given the root of a binary tree, return how many nodes have a value equal to the average of the values in their subtree.
A node's subtree is the node together with all of its descendants. The average of k values is their sum divided by k, rounded down to an integer.
Example 1
Input: root = [4,8,5,0,1,null,6]
Output: 5
Explanation: 4: (4+8+5+0+1+6) / 6 = 4. 5: (5+6) / 2 = 5. 0, 1 and 6 are leaves. 8: (8+0+1) / 3 = 3, not 8. Five nodes match.
Example 2
Input: root = [1]
Output: 1
Explanation: A leaf always equals its own average.
Example 3
Input: root = [2,1,4]
Output: 3
Explanation: The root's average is 7 / 3 = 2 (rounded down), and both leaves match too.
Constraints
1 <= number of nodes <= 10000 <= Node.val <= 1000
Hints for Count Nodes Equal to Average of Subtree
Hint 1
A subtree's average needs only two numbers: its sum and its size.
Hint 2
Both combine from the children: sum = left sum + right sum + value, size = left size + right size + 1.
Hint 3
Compute them in one post-order walk and compare
sum / size(integer division) with the node's value as you go.
How to solve Count Nodes Equal to Average of Subtree
A post-order walk returns each subtree's sum and size, built from its children's; the node is counted when the integer average equals its value.
Approach
walk(node)returns(sum, size); a null node returns(0, 0).- For a node, combine its children's pairs into
sum = ls + rs + valandsize = lc + rc + 1. - If
sum / size(rounded down) equalsval, increase the count. - Return
(sum, size); the count after walking the root is the answer.
Why it works
Each subtree is the disjoint union of the node and its two child subtrees, so the sums and sizes add up exactly. Every node is visited once, after its children, so its pair is ready when it is tested.
Complexity
- Time —
O(n) - Space —
O(h) for the recursion
Pitfalls
- Recomputing each subtree's sum from scratch is O(n^2).
- Round down: values are non-negative, so plain integer division does it.
Reference solution
Python
from typing import Optional
def averageOfSubtree(root: Optional[TreeNode]) -> int:
count = 0
def walk(node):
nonlocal count
if node is None:
return 0, 0
ls, lc = walk(node.left)
rs, rc = walk(node.right)
s = ls + rs + node.val
c = lc + rc + 1
if s // c == node.val:
count += 1
return s, c
walk(root)
return countJava
public static int averageOfSubtree(TreeNode root) {
int[] count = new int[1];
avgWalk(root, count);
return count[0];
}
// Returns {sum, size} of the subtree.
static int[] avgWalk(TreeNode node, int[] count) {
if (node == null) return new int[] {0, 0};
int[] l = avgWalk(node.left, count), r = avgWalk(node.right, count);
int s = l[0] + r[0] + node.val, c = l[1] + r[1] + 1;
if (s / c == node.val) count[0]++;
return new int[] {s, c};
}C++
pair<int, int> avgWalk(TreeNode* node, int& count);
int averageOfSubtree(TreeNode* root) {
int count = 0;
avgWalk(root, count);
return count;
}
// Returns {sum, size} of the subtree.
pair<int, int> avgWalk(TreeNode* node, int& count) {
if (!node) return {0, 0};
auto l = avgWalk(node->left, count);
auto r = avgWalk(node->right, count);
int s = l.first + r.first + node->val, c = l.second + r.second + 1;
if (s / c == node->val) count++;
return {s, c};
}JavaScript
var averageOfSubtree = function(root) {
var state = { count: 0 };
avgWalk(root, state);
return state.count;
};
// Returns [sum, size] of the subtree.
var avgWalk = function(node, state) {
if (node === null) return [0, 0];
var l = avgWalk(node.left, state), r = avgWalk(node.right, state);
var s = l[0] + r[0] + node.val, c = l[1] + r[1] + 1;
if (Math.floor(s / c) === node.val) state.count++;
return [s, c];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals