Count Nodes Equal to Average of Subtree - Video Solutions
Count Nodes Equal to Average of Subtree | 2 Approaches | Leetcode-2265 | Explanation ➕ Live Coding
Count Nodes Equal to Average of Subtree - Video Solution
Watch 10 video solutions for Count Nodes Equal to Average of Subtree, a medium level problem involving Tree, Depth-First Search, Binary Tree. This walkthrough by codestorywithMIK has 7,344 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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.
Note:
- The average of
nelements is the sum of thenelements divided bynand rounded down to the nearest integer. - A subtree of
rootis a tree consisting ofrootand all of its descendants.
Example 1:
Input: root = [4,8,5,0,1,null,6] Output: 5 Explanation: For the node with value 4: The average of its subtree is (4 + 8 + 5 + 0 + 1 + 6) / 6 = 24 / 6 = 4. For the node with value 5: The average of its subtree is (5 + 6) / 2 = 11 / 2 = 5. For the node with value 0: The average of its subtree is 0 / 1 = 0. For the node with value 1: The average of its subtree is 1 / 1 = 1. For the node with value 6: The average of its subtree is 6 / 1 = 6.
Example 2:
Input: root = [1] Output: 1 Explanation: For the node with value 1: The average of its subtree is 1 / 1 = 1.
Constraints:
- The number of nodes in the tree is in the range
[1, 1000]. 0 <= Node.val <= 1000
Approach Overview
Problem Overview: You are given the root of a binary tree. For every node, compute the average value of all nodes in its subtree (including itself). Count how many nodes have a value equal to the integer average of their subtree.
Approach 1: Recursion with Post-Order Traversal (O(n) time, O(h) space)
This approach uses a post-order Depth-First Search to process children before their parent. Each recursive call returns two values: the sum of the subtree and the number of nodes in that subtree. With these values, you compute average = sum // count and compare it with the current node's value. Because each node is visited exactly once and aggregation happens while returning from recursion, the algorithm runs in O(n) time with O(h) space for the recursion stack, where h is the tree height. This pattern is common in tree problems where subtree metrics must be combined bottom-up.
Approach 2: Iterative DFS Using Stack (O(n) time, O(n) space)
An iterative solution simulates the same post-order traversal using an explicit stack instead of recursion. Each stack frame stores the node and a state flag indicating whether its children have already been processed. A hash map (or dictionary) stores computed (sum, count) pairs for each node so the parent can aggregate them later. Once both children are processed, compute the subtree sum and node count, then check whether the node value equals sum // count. This method avoids recursion depth limits but uses O(n) auxiliary space for the stack and cached results.
Recommended for interviews: The recursive post-order traversal is the expected solution. Interviewers want to see that you recognize subtree computations require bottom-up aggregation, a common binary tree pattern. The iterative stack version demonstrates deeper understanding of DFS mechanics but is usually unnecessary unless recursion limits are a concern.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursion with Post-Order Traversal | O(n) | O(h) | Best general solution. Clean bottom-up aggregation of subtree sum and count. |
| Iterative DFS Using Stack | O(n) | O(n) | When recursion depth may overflow or when implementing DFS iteratively. |