2265. Count Nodes Equal to Average of Subtree

Tree
DFS
Binary Tree
Recursion

TIME

O(n)

SPACE

O(h)

Intuition

Each node's test needs two facts about its own subtree: the sum of the values and how many there are. Both are simple aggregates of the same facts for the left and right subtrees, so a single post-order traversal can compute them bottom-up and answer every node on the way back.

Post-order is forced here rather than chosen. A node cannot be checked until its children have reported their totals, so the recursion has to descend first and do its work while unwinding.

Returning the pair (sum, count) up the call chain is what keeps this linear. Computing the subtree sum separately at each node would re-walk the same descendants once per ancestor and degrade to O(n * h).

Approach

Define dfs(node) returning (sum, count) for the subtree rooted at node.
- Empty node returns (0, 0), which makes a leaf's arithmetic fall out naturally.
Recurse left and right, then combine:
- total = leftSum + rightSum + node.val
- count = leftCount + rightCount + 1
If node.val == total // count, increment the answer. Integer division is already the floor the problem asks for, since all values are non-negative.
Return (total, count) to the caller.
The answer is the running count after the traversal finishes.

Complexity

Time: O(n), every node visited once, O(1) work each
Space: O(h) recursion stack, up to O(n) for a fully skewed tree

Edge Cases

Single node → its own average is itself → 1 (Example 2)
Every leaf always matches, since val / 1 == val; a tree of L leaves scores at least L
Values may be 0, so 0 / 1 == 0 counts (Example 1 includes it)
Averages are floored, so a node like 5 with subtree sum 11 over 2 nodes matches
Max subtree sum is 1000 * 1000 = 10^6, comfortably inside int
Skewed trees reach depth 1000, which stays within default recursion limits

Code

from typing import Optional, Tuple


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right


class Solution:
    def averageOfSubtree(self, root: Optional["TreeNode"]) -> int:
        """
        2265. Count Nodes Equal to Average of Subtree
        Time: O(n)
        Space: O(h)
        """
        self.answer = 0

        def dfs(node: Optional["TreeNode"]) -> Tuple[int, int]:
            # returns (sum of subtree values, number of nodes)
            if node is None:
                return 0, 0

            left_sum, left_count = dfs(node.left)
            right_sum, right_count = dfs(node.right)

            total = left_sum + right_sum + node.val
            count = left_count + right_count + 1

            # values are non-negative, so // is the required floor
            if node.val == total // count:
                self.answer += 1

            return total, count

        dfs(root)
        return self.answer

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

/**
 * 2265. Count Nodes Equal to Average of Subtree
 * Time: O(n)
 * Space: O(h)
 */
class Solution {
    private int answer = 0;

    public int averageOfSubtree(TreeNode root) {
        dfs(root);
        return answer;
    }

    /** Returns {sum of subtree values, number of nodes}. */
    private int[] dfs(TreeNode node) {
        if (node == null) {
            return new int[]{0, 0};
        }

        int[] left = dfs(node.left);
        int[] right = dfs(node.right);

        int total = left[0] + right[0] + node.val;
        int count = left[1] + right[1] + 1;

        // values are non-negative, so integer division is the required floor
        if (node.val == total / count) {
            answer++;
        }

        return new int[]{total, count};
    }
}