Count Nodes Equal to Average of Subtree — LeetCode 2265 Postorder DFS

Problem Statement#

Given the root of a binary tree, return the number of nodes where the node value equals the floor of the average of all values in its subtree. The subtree of a node includes the node itself.

Constraints:

• Number of nodes is in [1, 1000].
• 0 <= Node.val <= 1000.
• Average uses integer (floor) division.

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

Why This Problem Matters#

LeetCode 2265 "Count Nodes Equal to Average of Subtree" is a beloved Amazon and Google warm-up because it tests whether you can compose two postorder aggregates (sum and count) in a single pass. Many candidates instinctively reach for two traversals — one to compute averages, one to compare — wasting time. The single-pass solution is the canonical way to demonstrate clean tree DP.

The Core Insight#

For each node, the parent only needs two numbers: the sum of values in this subtree and the count of nodes. With those, the parent can compute its own subtree sum and count by adding its value and 1. Compare sum // count to node.val at every node and increment a counter when they match.

Visual Dry Run#

Tree [4,8,5,0,1,null,6].

Wait — recompute: nodes are 0,1,8,6,5,4. The root is 4 with subtree sum 4+8+0+1+5+6 = 24 and count 7, average 3, no match. Total matches: 0, 1, 6, 5, and root via separate recompute. Actual answer is 5 because 4 also matches when its subtree of 4,8,5,0,1,6 sums to 24/6 = 4. Let me revise: subtree count of root is 6, not 7. With sum 24 and count 6, avg = 4 = root.val, so root matches.

Solution (Optimal)#

class Solution:
    def averageOfSubtree(self, root):
        self.count = 0
        def dfs(node):
            if not node:
                return 0, 0
            ls, lc = dfs(node.left)
            rs, rc = dfs(node.right)
            total_sum = ls + rs + node.val
            total_count = lc + rc + 1
            if total_sum // total_count == node.val:
                self.count += 1
            return total_sum, total_count
        dfs(root)
        return self.count

var averageOfSubtree = function(root) {
    let count = 0;
    const dfs = (node) => {
        if (!node) return [0, 0];
        const [ls, lc] = dfs(node.left);
        const [rs, rc] = dfs(node.right);
        const total = ls + rs + node.val;
        const c = lc + rc + 1;
        if (Math.floor(total / c) === node.val) count++;
        return [total, c];
    };
    dfs(root);
    return count;
};

Time: O(n) — every node processed once. Space: O(h) — recursion stack proportional to tree height.

Common Mistakes#

• Using regular division in Python or JavaScript instead of floor division.
• Returning only sum and recomputing count via a separate traversal — doubles the runtime constant.
• Mutating a global counter while also returning it from dfs — confusing and error-prone.
• Forgetting to handle the null base case which should return (0, 0).
• Counting nodes whose floor average equals the node value with off-by-one errors when subtree count includes or excludes the node itself.

Interview Tips#

• State the postorder pattern explicitly: "I will return (sum, count) from each subtree".
• Mention that returning a tuple avoids two traversals.
• For very large trees, recursion depth could be an issue — bring up an iterative postorder if asked.
• The integer division detail is often a source of subtle bugs — call it out.

Follow-up Questions#

• Streaming version: average updated as new nodes insert. Hint: maintain running sum and count per subtree.
• Equal to median instead of mean: harder because median is not associative. Hint: use balanced BSTs per subtree.
• Weighted nodes: include weights in the average. Hint: track weighted sum and weight count.
• Multi-rooted forest: apply DFS from every root. Hint: iterate roots, accumulate count.
• Threshold version: count nodes where average is within k of value. Hint: replace equality check.

Key Takeaways#

• LeetCode 2265 is a classic single-pass postorder DFS.
• Return (sum, count) from every recursive call to avoid retraversal.
• Floor division is the official aggregation rule — use // in Python and Math.floor in JS.
• Time is O(n), space is O(h) for the recursion stack.
• The pattern generalizes to any subtree-aggregate-vs-node-property comparison.
• Common at Amazon, Google, and Microsoft as a warm-up before harder tree DP.
• Bringing up tuple-return tree DP earns instant credit during onsites.