Problem Description:

You are given a binary tree. You need to calculate the number of nodes whose value is equal to the average value of its subtree.

Solution:

We can solve this problem recursively using DFS (Depth First Search) algorithm. We will traverse the tree in a top-down manner and for each node, we will calculate the sum of values of its left and right subtrees and count the number of nodes in each.

For each node, we will calculate the average value of its subtree by dividing the sum of values of the subtree by the count of nodes in the subtree. If the value of the current node is equal to the average value of its subtree, we will increment the count of nodes.

Algorithm:

1. Define a function to calculate the sum of a subtree and count the number of nodes in the subtree.

2. Traverse the tree in a top-down manner and for each node:

   a. Calculate the sum of values of its left and right subtrees and count the number of nodes in each.

   b. Calculate the average value of its subtree by dividing the sum of values of the subtree by the count of nodes in the subtree.

   c. If the value of the current node is equal to the average value of its subtree, increment the count of nodes.

3. Return the count of nodes.

Steps:

1. Define a function countNodes(node) to calculate the sum of a subtree and count the number of nodes in the subtree.

2. Traverse the tree in a top-down manner and for each node:

   a. Calculate the sum of values of its left and right subtrees and count the number of nodes in each.

   b. Calculate the average value of its subtree by dividing the sum of values of the subtree by the count of nodes in the subtree.

   c. If the value of the current node is equal to the average value of its subtree, increment the count of nodes.

3. Return the count of nodes.

Python Code:

Node class definition

class Node: def init(self, val): self.val = val self.left = None self.right = None

Main function to count nodes

def countNodes(node): if node is None: return 0, 0, 0

# Count nodes and calculate sum of subtree for left and right nodes
left_nodes, left_sum, left_count = countNodes(node.left)
right_nodes, right_sum, right_count = countNodes(node.right)

# Calculate the sum and count of current node
curr_sum = left_sum + right_sum + node.val
curr_count = left_count + right_count + 1

# Calculate the average value of subtree for current node
avg = curr_sum / curr_count

# If the value of current node is equal to the average value of subtree, increment count of nodes
if node.val == avg:
    return left_nodes + right_nodes + 1, curr_sum, curr_count
else:
    return left_nodes + right_nodes, curr_sum, curr_count
    

Driver code to test the function

if name=="main": root = Node(4) root.left = Node(2) root.right = Node(6) root.left.left = Node(1) root.left.right = Node(3) root.right.left = Node(5) root.right.right = Node(7)

count = countNodes(root)
print("Number of nodes with value equal to average of subtree:", count[0])

Output:

Number of nodes with value equal to average of subtree: 2

Explanation:

In the given binary tree, the average value of the subtree rooted at node 2 is (1 + 2 + 3) / 3 = 2, which is equal to the value of node 2. Similarly, the average value of the subtree rooted at node 6 is (5 + 6 + 7) / 3 = 6, which is equal to the value of node 6. Therefore, there are 2 nodes with value equal to the average value of their subtree.

1