Similar Problems
Similar Problems not available
Count Nodes Equal To Average Of Subtree  Leetcode Solution
Companies:
LeetCode: Count Nodes Equal To Average Of Subtree Leetcode Solution
Difficulty: Medium
Topics: tree binarytree depthfirstsearch
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 topdown 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:

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

Traverse the tree in a topdown 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.

Return the count of nodes.
Steps:

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

Traverse the tree in a topdown 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.

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.
Count Nodes Equal To Average Of Subtree Solution Code
1