Count Nodes Equal to Average of Subtree

Count Nodes Equal to Average of Subtree

What is this problem about?

In this tree problem, you need to count how many nodes in a binary tree have a value equal to the average of all the values in their subtree. The average is calculated as the sum of all node values in the subtree divided by the number of nodes in the subtree, rounded down to the nearest integer.

Why is this asked in interviews?

This is a standard "Medium" tree question asked by Microsoft and Google to test Depth-First Search (DFS) skills. It requires you to aggregate information from the bottom up. It evaluations your ability to return multiple values (sum and count) from a recursive function and perform calculations based on those values at each node.

Algorithmic pattern used

This problem uses the Post-order Traversal (DFS) pattern. Since a node's average depends on its children's subtrees, you must process the children first. Each recursive call returns a pair: {sum_of_values, count_of_nodes} for the subtree rooted at that node. At the current node, you calculate the total sum and count, compute the average, and increment a global counter if it matches the node's value.

Example explanation

Subtree:

    4
   / 
  8   5
 / \   
0   1   6

• For node 0: sum=0, count=1. Avg=0. Match!
• For node 1: sum=1, count=1. Avg=1. Match!
• For node 8: sum=0+1+8=9, count=3. Avg=9/3=3. No match.
• For node 6: sum=6, count=1. Avg=6. Match!
• For node 5: sum=6+5=11, count=2. Avg=11/2=5. Match!
• For root 4: sum=9+11+4=24, count=6. Avg=24/6=4. Match! Total count: 5.

Common mistakes candidates make

A common mistake is performing a separate traversal for each node to calculate its subtree average, which leads to $O(n^2)$ complexity. Another mistake is using floating-point division when integer division (truncation) is requested. Failing to handle the base case (null nodes) correctly can also lead to errors.

Interview preparation tip

Practice returning custom objects or arrays from recursive functions. Tree problems that require "bottom-up" aggregation are extremely common, and being able to pass multiple pieces of information up the tree is a vital skill.