2265. Count Nodes Equal to Average of Subtree
Asked at Snowflake
Difficulty
Medium
Time
O(n)
Space
O(h)
Pattern
Tree
Companies
1
Problem
You are given the root of a binary tree. For every node, look at its subtree — that node plus all of its descendants. Compute the average value of that subtree, rounded down to an integer. Count how many nodes have a value equal to that rounded average, and return that count.
The average of n values is their sum divided by n, with the result floored. A leaf is a subtree of size 1, so its average is just its own value — every leaf always counts.
A simple way is to walk the tree and, for each node, gather all values below it. That is slow on a long chain of nodes. The fast way is one post-order DFS that returns each subtree's sum and size, so a parent can combine its two children in O(1).
Every node has its own subtree average
Constraints
- ●
The number of nodes in the tree is in the range [1, 1000]. - ●
0 <= Node.val <= 1000
Examples
root = [4,8,5,0,1,null,6]5root = [1]1Asked At
1 companies| Company | Difficulty | |
|---|---|---|
| Snowflake | Medium | View all Snowflake questions → |
How to Think About It
Computing the sum and size of every subtree separately is O(n²) on a skewed tree.
Key insight: a node's subtree sum is left sum + right sum + node.val and its size is left size + right size + 1. So return (sum, size) from a post-order DFS.
At each node, compare node.val with sum // size and increment a counter if they are equal.
Values are non-negative, so floor division behaves as expected in every language.
Walkthrough for a leaf: sum = its value, size 1, average = its value -> every leaf counts.
Optimal Approach
Step 1: count = 0.
Step 2: dfs(node) returns (sum, size):
Null -> (0, 0).
(ls, lc) = dfs(left), (rs, rc) = dfs(right).
s = ls + rs + node.val, c = lc + rc + 1.
If s // c == node.val, count += 1.
Return (s, c).
Step 3: Return count.
Time: O(n). Space: O(h).
Post-order DFS returns (sum, size)
What Trips People Up in Real Interviews
Recomputing subtree sums for every node from scratch.
Rounding the average instead of flooring it.
Excluding the node itself from its own subtree average.
Using floating-point division and comparing doubles.
Solution Code
O(n) timedef averageOfSubtree(root):
count = 0
def dfs(node):
nonlocal count
if not node:
return 0, 0
ls, lc = dfs(node.left)
rs, rc = dfs(node.right)
s = ls + rs + node.val
c = lc + rc + 1
if s // c == node.val:
count += 1
return s, c
dfs(root)
return countFrequently Asked Questions
What is the Count Nodes Equal to Average of Subtree problem?
Count Nodes Equal to Average of Subtree asks how many nodes have a value equal to the (floored) average of all values in their subtree, including themselves. A single post-order traversal that returns each subtree's sum and size answers it in linear time.
How do you solve Count Nodes Equal to Average of Subtree?
The optimal approach runs in O(n) time and O(h) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Count Nodes Equal to Average of Subtree?
Count Nodes Equal to Average of Subtree is asked at Snowflake. It is a medium difficulty problem.
What are common mistakes on Count Nodes Equal to Average of Subtree?
- Recomputing subtree sums for every node from scratch.
- Rounding the average instead of flooring it.
- Excluding the node itself from its own subtree average.
- Using floating-point division and comparing doubles.