We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Nodes Equal to Average of Subtree

Difficulty: Medium

Problem Description

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. The average of n elements is the sum of the n elements divided by n and rounded down to the nearest integer. A subtree of root is a tree consisting of root and all of its descendants.

Key Insights

  • Each node's value is compared to the average of all values in its subtree.
  • The average is calculated as the total sum of node values in the subtree divided by the number of nodes.
  • The algorithm requires a depth-first traversal of the tree to compute the sum and count of nodes in each subtree.

Space and Time Complexity

Time Complexity: O(N) - where N is the number of nodes in the tree, as we visit each node once. Space Complexity: O(H) - where H is the height of the tree, due to the recursive call stack.

Solution

To solve the problem, we will use a depth-first search (DFS) approach. We will traverse each node in the binary tree, calculating the sum of values and the count of nodes in its subtree. After calculating these values, we will check if the value of the current node is equal to the average (sum divided by count). If it is, we will increment our result counter.

The data structures involved are:

  • A binary tree node structure to represent each node.
  • Recursion to perform the depth-first traversal.

The algorithm works as follows:

  1. Define a recursive function that calculates the sum of values and the count of nodes in the subtree.
  2. For each node, calculate the average and compare it to the node's value.
  3. Return the total count of nodes that satisfy the condition.

Code Solutions

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def averageOfSubtree(self, root: TreeNode) -> int:
        self.count = 0
        
        def dfs(node):
            if not node:
                return (0, 0)  # (sum, count)
            left_sum, left_count = dfs(node.left)
            right_sum, right_count = dfs(node.right)
            total_sum = left_sum + right_sum + node.val
            total_count = left_count + right_count + 1
            
            # Calculate average and compare with node value
            if total_sum // total_count == node.val:
                self.count += 1
            
            return (total_sum, total_count)

        dfs(root)
        return self.count
← Back to All Questions