#2265

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Count Nodes Equal to Average of Subtree

Given a binary tree, count nodes where the value equals the average of values in its subtree.

Problem Statement

Given the root of a binary tree, return the number of nodes where the value of the node is equal to the average of the values in its subtree. A subtree is defined as any node and all of its descendants, with the average calculated by dividing the sum of node values in that subtree by the number of nodes.

To solve this, perform a depth-first search traversal while maintaining the sum and count of nodes for each subtree. After traversing a subtree, check if the node’s value matches the average and increment the result counter accordingly.

Examples

Example 1

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

Output: 5

For the node with value 4: The average of its subtree is (4 + 8 + 5 + 0 + 1 + 6) / 6 = 24 / 6 = 4. For the node with value 5: The average of its subtree is (5 + 6) / 2 = 11 / 2 = 5. For the node with value 0: The average of its subtree is 0 / 1 = 0. For the node with value 1: The average of its subtree is 1 / 1 = 1. For the node with value 6: The average of its subtree is 6 / 1 = 6.

Example 2

Input: root = [1]

Output: 1

For the node with value 1: The average of its subtree is 1 / 1 = 1.

Constraints

The number of nodes in the tree is in the range [1, 1000].
0 <= Node.val <= 1000

Solution Approach

DFS Traversal with State Tracking

The problem can be solved using a depth-first search traversal. For each node, calculate the sum and the count of nodes in its subtree. Compare the node's value to the average and return the count of nodes that match the average.

Efficient Average Calculation

To calculate the average of a subtree, the sum of the node values and the count of nodes are tracked during the DFS. This allows each node's average to be computed in constant time after the subtree sum and count are known.

Recursive Solution

The problem naturally lends itself to a recursive approach where each node’s value is checked against the average of its subtree. The recursion ensures that every node’s subtree is fully traversed before calculating averages.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(N) where N is the number of nodes in the tree, as each node is visited once during the DFS. The space complexity is also O(N) due to the recursion stack in the worst case (a skewed tree).

What Interviewers Usually Probe

Look for knowledge of depth-first search traversal.
Ensure the candidate can track both sum and count during traversal.
Check for clarity in recursive state maintenance during traversal.

Common Pitfalls or Variants

Common pitfalls

Failing to account for the correct subtree sum and count for each node.
Incorrectly updating the result when a node's value doesn't match the average.
Not handling edge cases such as a single-node tree properly.

Follow-up variants

Different binary tree traversal methods such as BFS instead of DFS.
Handling trees with negative or very large node values.
Optimizing space complexity for larger trees or restricted environments.

FAQ

What is the key approach for solving the Count Nodes Equal to Average of Subtree problem?

The key approach is performing a depth-first search traversal while maintaining the sum and count of nodes in each subtree, then comparing each node's value to the average of its subtree.

How can recursion help in solving this problem?

Recursion helps by allowing the traversal of each subtree, ensuring the sum and count of each node's subtree are calculated before the average is checked.

What is the time complexity of this problem?

The time complexity is O(N), where N is the number of nodes, because each node is visited once during the depth-first traversal.

What is the space complexity of the Count Nodes Equal to Average of Subtree problem?

The space complexity is O(N) due to the recursion stack, which can grow up to the height of the tree in the worst case.

Are there any edge cases to consider in this problem?

Yes, edge cases include a tree with just one node, or trees with skewed structures that affect the depth of recursion.

terminal

Solution

Solution 1: DFS

We design a function $\textit{dfs}$, which calculates the sum and the number of nodes of the subtree rooted at the current node.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def averageOfSubtree(self, root: TreeNode) -> int:
        def dfs(root) -> tuple:
            if not root:
                return 0, 0
            ls, ln = dfs(root.left)
            rs, rn = dfs(root.right)
            s = ls + rs + root.val
            n = ln + rn + 1
            nonlocal ans
            ans += int(s // n == root.val)
            return s, n

        ans = 0
        dfs(root)
        return ans

Continue Practicing

#2331 evaluate boolean binary tree #2385 amount of time for binary tree to be infected #2415 reverse odd levels of binary tree