Check tree nodes equal subtree average

Question

LeetCode 2265. Count Nodes Equal to Average of Subtree – Adapted: Verify that every node’s value equals the average of all values in its subtree.

https://leetcode.com/problems/count-nodes-equal-to-average-of-subtree/description/

Verify Nodes Equal Subtree Average

Given a binary tree, return true if every node's value equals the integer average of all values in its subtree (including itself). The average is defined as floor(sum_of_values / number_of_nodes). Otherwise, return false. The tree is provided in level-order as an array where null represents a missing child. An empty tree should return true.

Constraints

• 0 <= n <= 100000 (n is the number of entries in the level-order array)
• -10^9 <= node value <= 10^9
• Input uses level-order with null for missing children
• Empty tree ([]) should return true
• Time: O(n), Space: O(n)

Examples

Example 1

Input: level = [2,1,3]
Output: true

Explanation: Leaves (1 and 3) match their averages. Root has sum=2+1+3=6, count=3, average=2; matches.

Example 2

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

Explanation: Node 8 has subtree sum=9, count=3, average=3; 8 != 3, so the tree fails.

Hints

1. Use a post-order traversal to compute (sum, count) for each subtree.
2. For each node, check node.val == (subtree_sum // subtree_count).
3. Building the tree from the level-order array can be done with a queue.

Approach

We first construct the binary tree from the level-order list using a queue, interpreting null as a missing child. To verify the condition for every node, we perform an iterative post-order traversal. For each node, we compute the sum and count of its subtree from its children and check whether node.val equals floor(sum / count). We store (sum, count, ok) per node in a dictionary to avoid recursion and ensure O(n) time and O(n) space.

• Time complexity: O(n)
• Space complexity: O(n)