This is our solution and implementation to problem #2265: Count Nodes Equal to Average of Subtree on LeetCode.
Our code is written in Java. If you want to code your solution in a different language, no worries, as the core concepts will carry over from language to language. This page includes our analysis of the problem, our implementation strategy a breakdown on the space and time complexity, and the full code implementation.
If you would like to view the original problem and solve it, please visit: Count Nodes Equal to Average of Subtree on LeetCode.
Problem Analysis
We need to assess the average of each subtree. We can use a recursive approach, but we must be careful; we cannot simply average the values of the left and right subtrees, since they may have different amounts of nodes. We can instead keep track of a running sum and number of nodes, then calculate the average when needed.
Implementation Strategy
We will use a depth first search to determine the sums and number of nodes in each left and right subtree of each node, then combine those values with each node. Then, we will calculate the average for that node, and if it is equal to its value, increment a counter.
Space and Time Complexity
The time complexity is O(n), where n is the number of nodes. The space complexity is O(log n) because of the recursion stack.
Additional Resources
The links below outline some of the points discussed above in more detail.
Full Code
Our solution is given in the Java code below:
All of our solutions are hosted on GitHub. The code on this page was pulled from the repo.