Count Nodes Equal to Average of Subtree solution and explanation
Google
9 more videos on this problem
Count Nodes Equal to Average of Subtree | 2 Approaches | Leetcode-2265 | Explanation ➕ Live CodingcodestorywithMIK · 24:13 · 7K views
2265. Count Nodes Equal to Average of Subtree || Find Sum, Count, Average in O(n) timeAryan Mittal · 9:47 · 2K views
COUNT NODES EQUAL TO AVERAGE OF SUBTREE | LEETCODE 2265 | PYTHON DFS SOLUTIONCracking FAANG · 11:41 · 2K views
2265 Count Nodes Equal to Average of Subtree | Zero to FAANG | Solution | Leetcode | Striver | WE2Programmers Zone · 17:13 · 2K views
2265. Count Nodes Equal to Average of Subtree (Leetcode Medium)Programming Live with Larry · 10:41 · 887 views
Leetcode 2265 - Count Nodes Equal to Average of SubtreeMarcio Marinho · 9:16 · 557 views
Daily Leetcode #1311: Nov 02, 2023 - 2265. Count Nodes Equal to Average of SubtreeProgramming Live with Larry · 5:45 · 323 views
Count Nodes Equal to Average of Subtree - LeetCode 2265 - PythonAlpha-Code · 12:04 · 220 views
Solving LeetCode 2265 Count Nodes Equal to Average of Subtree | Post order traversalCode Harmony · 10:15 · 159 views
Count Nodes Equal to Average of Subtree - LeetCode 2265 - Java Solutionalgobest - Computer Science · 2:51 · 108 views
The problem
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.
Approach 1: Recursion with Post-Order Traversal
This approach involves using a post-order traversal (left, right, root) to compute the sum and count of nodes for each subtree. At each node, the sum of values and the total count of the subtree nodes are determined. The average is calculated by dividing the sum by the count and compared with the node's value. If they are equal, a counter is incremented.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def averageOfSubtree(self, root: TreeNode) -> int:
def dfs(node):
if not node:
return (0, 0)
left_sum, left_count = dfs(node.left)
right_sum, right_count = dfs(node.right)
total_sum = left_sum + right_sum + node.val
total_count = left_count + right_count + 1
if node.val == total_sum // total_count:
self.count += 1
return total_sum, total_count
self.count = 0
dfs(root)
return self.countclass TreeNode {
constructor(val = 0, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
function averageOfSubtree(root) {
let count = 0;
function dfs(node) {
if (!node) return [0, 0];
const [leftSum, leftCount] = dfs(node.left);
const [rightSum, rightCount] = dfs(node.right);
const totalSum = leftSum + rightSum + node.val;
const totalCount = leftCount + rightCount + 1;
if (node.val === Math.floor(totalSum / totalCount)) {
count++;
}
return [totalSum, totalCount];
}
dfs(root);
return count;
}This Python solution defines a recursive DFS function `dfs` that traverses the tree in a post-order manner. For each node, it computes the sum and count of the subtree rooted at that node. If the node value equals the average (sum // count) of its subtree, the counter `self.count` is incremented.
Time Complexity: O(n), where n is the number of nodes in the tree, as each node is visited once.
Space Complexity: O(h), where h is the height of the tree, which accounts for the recursion stack.
Approach 2: Iterative Using Stack
This approach involves using an iterative method with an explicit stack to perform a post-order traversal. Similar to the recursive method, it calculates the sum and count of the subtree nodes for each node using an additional data structure to simulate recursion.
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class Solution {
public int averageOfSubtree(TreeNode root) {
int count = 0;
Map<TreeNode, int[]> sumAndCount = new HashMap<>();
Stack<TreeNode> stack = new Stack<>();
Stack<Boolean> visited = new Stack<>();
stack.push(root);
visited.push(false);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
boolean isVisited = visited.pop();
if (node != null) {
if (isVisited) {
int leftSum = node.left != null ? sumAndCount.get(node.left)[0] : 0;
int leftCount = node.left != null ? sumAndCount.get(node.left)[1] : 0;
int rightSum = node.right != null ? sumAndCount.get(node.right)[0] : 0;
int rightCount = node.right != null ? sumAndCount.get(node.right)[1] : 0;
int totalSum = leftSum + rightSum + node.val;
int totalCount = leftCount + rightCount + 1;
sumAndCount.put(node, new int[]{totalSum, totalCount});
if (node.val == totalSum / totalCount) {
count++;
}
} else {
stack.push(node);
visited.push(true);
stack.push(node.right);
visited.push(false);
stack.push(node.left);
visited.push(false);
}
}
}
return count;
}
}public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
public int AverageOfSubtree(TreeNode root) {
int count = 0;
Stack<(TreeNode, bool)> stack = new Stack<(TreeNode, bool)>();
Dictionary<TreeNode, (int, int)> nodeData = new Dictionary<TreeNode, (int, int)>();
stack.Push((root, false));
while (stack.Count > 0) {
var (node, visited) = stack.Pop();
if (node != null) {
if (visited) {
int leftSum = node.left != null ? nodeData[node.left].Item1 : 0;
int leftCount = node.left != null ? nodeData[node.left].Item2 : 0;
int rightSum = node.right != null ? nodeData[node.right].Item1 : 0;
int rightCount = node.right != null ? nodeData[node.right].Item2 : 0;
int totalSum = leftSum + rightSum + node.val;
int totalCount = leftCount + rightCount + 1;
nodeData[node] = (totalSum, totalCount);
if (node.val == totalSum / totalCount) count++;
} else {
stack.Push((node, true));
stack.Push((node.right, false));
stack.Push((node.left, false));
}
}
}
return count;
}
}In this Java implementation, an iterative approach is employed using two stacks. The first stack manages the node traversal, while the second boolean stack keeps track of whether each node has been fully processed. A HashMap serves as a storage for each node's subtree sum and count.
Time Complexity: O(n), where n is the number of nodes, due to each node being pushed twice onto the stack.
Space Complexity: O(n), accounting for the stack and HashMap.
Approach 3: DFS
We design a function dfs, which calculates the sum and the number of nodes of the subtree rooted at the current node.
The execution process of the function dfs is as follows:
- If the current node is null, return
(0, 0). - Otherwise, we recursively calculate the sum and the number of nodes of the left and right subtrees, denoted as
(ls, ln)and(rs, rn), respectively. Then, the sumsand the number of nodesnof the subtree rooted at the current node arels + rs + root.valandln + rn + 1, respectively. Ifs / n = root.val, it means the current node meets the requirement of the problem, and we increment the answeransby1. - Finally, the function
dfsreturnssandn.
We initialize the answer ans to 0, then call the dfs function, and finally return the answer ans.
The time complexity is O(n), and the space complexity is O(n). Here, n represents the number of nodes in the binary tree.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int averageOfSubtree(TreeNode* root) {
int ans = 0;
auto dfs = [&](this auto&& dfs, TreeNode* root) -> pair<int, int> {
if (!root) {
return {0, 0};
}
auto [ls, ln] = dfs(root->left);
auto [rs, rn] = dfs(root->right);
int s = ls + rs + root->val;
int n = ln + rn + 1;
if (s / n == root->val) {
++ans;
}
return {s, n};
};
dfs(root);
return ans;
}
};/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function averageOfSubtree(root: TreeNode | null): number {
let ans: number = 0;
const dfs = (root: TreeNode | null): [number, number] => {
if (!root) {
return [0, 0];
}
const [ls, ln] = dfs(root.left);
const [rs, rn] = dfs(root.right);
const s = ls + rs + root.val;
const n = ln + rn + 1;
if (Math.floor(s / n) === root.val) {
++ans;
}
return [s, n];
};
dfs(root);
return ans;
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func averageOfSubtree(root *TreeNode) (ans int) {
var dfs func(root *TreeNode) (int, int)
dfs = func(root *TreeNode) (int, int) {
if root == nil {
return 0, 0
}
ls, ln := dfs(root.Left)
rs, rn := dfs(root.Right)
s, n := ls+rs+root.Val, ln+rn+1
if s/n == root.Val {
ans++
}
return s, n
}
dfs(root)
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Recursion with Post-Order Traversal | Time Complexity: O(n), where n is the number of nodes in the tree, as each node is visited once. |
| Iterative Using Stack | Time Complexity: O(n), where n is the number of nodes, due to each node being pushed twice onto the stack. |
| DFS | – |
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. |
Frequently asked questions
Is Count Nodes Equal to Average of Subtree easy or hard?
The problem is rated Medium because it requires recognizing a post-order traversal pattern and returning multiple values from each DFS call. The implementation is straightforward once you realize subtree sum and count must be computed before evaluating the parent node.
Count Nodes Equal to Average of Subtree Python/Java solution
Most implementations use a recursive helper that returns (sum, count) for each subtree. Python and JavaScript solutions typically implement concise DFS recursion, while Java and C# may also use iterative stack-based DFS to simulate post-order traversal.
How to solve Count Nodes Equal to Average of Subtree in O(n)?
Use post-order DFS to compute subtree statistics bottom-up. Each recursive call returns the subtree sum and node count. After processing left and right children, calculate the average using sum // count and compare it with the node value. Since each node contributes to exactly one calculation, the algorithm runs in O(n).
What is the best approach for Count Nodes Equal to Average of Subtree?
The optimal approach is post-order DFS traversal. For each node, compute the sum and number of nodes in its subtree, then check if node.val equals sum // count. Each node is processed once, giving O(n) time complexity with O(h) recursion space where h is the tree height.
Is Count Nodes Equal to Average of Subtree asked at Google/Amazon/Meta?
Tree aggregation problems using DFS appear frequently in interviews at companies like Amazon, Google, and Meta. Variants that require computing subtree sums, averages, or counts are common because they test understanding of post-order traversal and recursion patterns.
What data structure is used in Count Nodes Equal to Average of Subtree?
The main data structure is a binary tree. The algorithm relies on depth-first search traversal. The recursive version uses the call stack, while the iterative approach uses an explicit stack and optionally a hash map to store subtree results.
What is the time complexity of Count Nodes Equal to Average of Subtree?
The optimal solution runs in O(n) time because every node in the binary tree is visited exactly once during the DFS traversal. Space complexity is O(h) for recursion stack depth, where h is the height of the tree (O(log n) for balanced trees and O(n) for skewed trees).