Quick Overview

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.

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/

Overview: 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

  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.

Loading coding console...

Show the approach

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)