Count Nodes Equal to Average of Subtree
Asked at Snowflake
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.
Asked At
| 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).
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
def 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.