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)
Solution
from collections import deque
def all_nodes_equal_subtree_average(level):
# Build binary tree from level-order array (null -> None)
class TreeNode:
__slots__ = ("val", "left", "right")
def __init__(self, val):
self.val = val
self.left = None
self.right = None
if not level:
return True
if level[0] is None:
return True
root = TreeNode(level[0])
q = deque([root])
it = iter(level[1:])
while q:
node = q.popleft()
try:
lv = next(it)
except StopIteration:
break
if lv is not None:
node.left = TreeNode(lv)
q.append(node.left)
try:
rv = next(it)
except StopIteration:
break
if rv is not None:
node.right = TreeNode(rv)
q.append(node.right)
# Iterative post-order to compute (sum, count, ok) for each node
info = {} # node -> (sum, count, ok)
stack = [(root, False)]
while stack:
node, visited = stack.pop()
if node is None:
continue
if not visited:
stack.append((node, True))
stack.append((node.right, False))
stack.append((node.left, False))
else:
sl, cl, ol = info.get(node.left, (0, 0, True))
sr, cr, orr = info.get(node.right, (0, 0, True))
s = node.val + sl + sr
c = 1 + cl + cr
ok = ol and orr and (node.val == s // c)
info[node] = (s, c, ok)
return info[root][2]
Explanation
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).
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.