2265. Count Nodes Equal to Average of Subtree

Problem Overview

A node counts when its value equals the integer average of every node in its subtree.

Intuition

A node counts when its value equals the integer average of every node in its subtree. Postorder DFS returns each subtree sum and size, so a parent can combine both children in constant time and compare sum/count to its own value.

Algorithm

1Run DFS that returns (sum, count) for the current subtree.
2Null nodes return (0, 0).
3Sum children with the current value; count is 1 plus both child counts.
4If sum / count equals the node value, increment the answer.
5Return the pair upward so parents can reuse it.

Example Walkthrough

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

1.Leaves 0, 1, and 6 each match their own average.
2.Node 5 has subtree sum 11 and count 2, average 5.
3.Root 4 has sum 24 and count 6, average 4. Five nodes qualify.

Output: 5

Common Pitfalls

•Use integer division; the problem floors the average.
•One DFS is enough. Do not recompute subtree sums from scratch at every node.
•Include the node itself in both the sum and the count.
•Space is O(h) from recursion, not O(1), on skewed trees.

2265.cs

// Approach: Postorder DFS returns (subtree sum, node count). At each node,
// average is sum/count (integer divide). Count when it equals the node value.
// Complexity: O(n) time and O(h) extra space, h = tree height.
public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
    {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution
{
    private int ans;

    public int AverageOfSubtree(TreeNode root)
    {
        Dfs(root);
        return ans;
    }

    private (int sum, int count) Dfs(TreeNode node)
    {
        if (node == null)
            return (0, 0);

        var left = Dfs(node.left);
        var right = Dfs(node.right);

        int sum = node.val + left.sum + right.sum;
        int count = 1 + left.count + right.count;

        if (sum / count == node.val)
            ans++;

        return (sum, count);
    }
}

Was this solution helpful?