Check tree nodes equal subtree average
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
##### 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/
Quick Answer: This question evaluates binary tree traversal and recursion skills, along with the ability to aggregate subtree values and verify numeric relationships between a node and its 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)
Hints
- Use a post-order traversal to compute (sum, count) for each subtree.
- For each node, check node.val == (subtree_sum // subtree_count).
- Building the tree from the level-order array can be done with a queue.