Count Nodes Equal to Sum of Descendants solution and explanation
4 more videos on this problem
1973. Count Nodes Equal to Sum of Descendants - Week 5/5 Leetcode February ChallengeProgramming Live with Larry · 4:44 · 152 views
leetcode 1973. Count Nodes Equal to Sum of Descendants - RecursionCode-Yao · 8:28 · 75 views
Leetcode 1973. Count Nodes Equal to Sum of Descendants (post order traversal)LetsCode · 3:58 · 27 views
Leetcode 1973 值等于子节点值之和的节点数量 Count Nodes Equal to Sum of Descendants书森学院 · 3:49 · 21 views
leetcode 1973 Count Nodes Equal to Sum of Descendants RecursionCode-Yao · 10:28 · 16 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 sum of the values of its descendants.
A descendant of a node x is any node that is on the path from node x to some leaf node. The sum is considered to be 0 if the node has no descendants.
Example 1:
Input: root = [10,3,4,2,1] Output: 2 Explanation: For the node with value 10: The sum of its descendants is 3+4+2+1 = 10. For the node with value 3: The sum of its descendants is 2+1 = 3.
Example 2:
Input: root = [2,3,null,2,null] Output: 0 Explanation: No node has a value that is equal to the sum of its descendants.
Example 3:
Input: root = [0] Output: 1 For the node with value 0: The sum of its descendants is 0 since it has no descendants.
Constraints:
- The number of nodes in the tree is in the range
[1, 105]. 0 <= Node.val <= 105
Approach overview
Problem Overview: Given a binary tree, count how many nodes have a value equal to the sum of all their descendant nodes. Descendants include every node in the subtree excluding the node itself. The challenge is efficiently computing subtree sums while visiting each node.
Approach 1: Recompute Subtree Sum for Every Node (Brute Force) (Time: O(n2), Space: O(h))
Traverse every node in the tree and compute the sum of its descendants using a separate recursive function. For each node, run a DFS that sums all nodes in its left and right subtrees, then compare that sum with the current node value. If they match, increment the counter. This approach repeatedly recalculates subtree sums, causing the same nodes to be visited many times.
The method uses a standard tree traversal and a helper function to compute subtree totals. On a skewed tree, each node may trigger a traversal of nearly the entire remaining tree. That leads to O(n^2) time in the worst case. Space usage is O(h) from the recursion stack, where h is the tree height.
Approach 2: Postorder DFS with Subtree Sum Propagation (Optimal) (Time: O(n), Space: O(h))
The efficient solution computes subtree sums during a single traversal using postorder DFS. Visit the left subtree, then the right subtree, then process the current node. Each recursive call returns the total sum of the subtree rooted at that node.
At each node, combine the sums returned from the left and right children. That value represents the sum of all descendants. Compare it with the node's value and increment the result if they match. Then return node.val + leftSum + rightSum so the parent can continue building the total.
This technique ensures each node contributes to the subtree sum exactly once. The algorithm relies on depth-first search over a binary tree. Because each node is processed a single time, the total runtime is O(n). Memory usage comes only from recursion depth, which is O(h).
Recommended for interviews: Interviewers expect the postorder DFS approach. It demonstrates that you recognize subtree computations should flow from children to parent. Starting with the brute force method shows understanding of the problem, but optimizing it to a single traversal proves you know how to eliminate repeated work in tree problems.
Solution
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def equalToDescendants(self, root: Optional[TreeNode]) -> int:
def dfs(root):
if root is None:
return 0
l, r = dfs(root.left), dfs(root.right)
if l + r == root.val:
nonlocal ans
ans += 1
return root.val + l + r
ans = 0
dfs(root)
return ans/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private int ans;
public int equalToDescendants(TreeNode root) {
dfs(root);
return ans;
}
private int dfs(TreeNode root) {
if (root == null) {
return 0;
}
int l = dfs(root.left);
int r = dfs(root.right);
if (l + r == root.val) {
++ans;
}
return root.val + l + r;
}
}/**
* 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 equalToDescendants(TreeNode* root) {
int ans = 0;
function<long long(TreeNode*)> dfs = [&](TreeNode* root) -> long long {
if (!root) {
return 0;
}
auto l = dfs(root->left);
auto r = dfs(root->right);
ans += l + r == root->val;
return root->val + l + r;
};
dfs(root);
return ans;
}
};/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func equalToDescendants(root *TreeNode) (ans int) {
var dfs func(*TreeNode) int
dfs = func(root *TreeNode) int {
if root == nil {
return 0
}
l, r := dfs(root.Left), dfs(root.Right)
if l+r == root.Val {
ans++
}
return root.Val + l + r
}
dfs(root)
return
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recompute Subtree Sum for Each Node (Brute Force) | O(n^2) | O(h) | Useful for understanding the problem before optimizing or when the tree is very small |
| Postorder DFS with Subtree Sum Propagation | O(n) | O(h) | Best general solution; processes each node once and avoids repeated subtree calculations |
Frequently asked questions
Is Count Nodes Equal to Sum of Descendants easy or hard?
The problem is generally classified as Medium. The core difficulty is recognizing that subtree sums should be computed with postorder traversal so each node is processed once. Once that insight is clear, the implementation becomes straightforward.
Count Nodes Equal to Sum of Descendants Python/Java solution
Implement a recursive DFS function that returns the subtree sum. For each node, compute leftSum and rightSum, compare their total with node.val, and increment a counter if they match. The same logic works in Python, Java, C++, and Go with O(n) time complexity.
How to solve Count Nodes Equal to Sum of Descendants in O(n)?
Use a postorder DFS that returns the sum of each subtree. First compute the sum from the left child, then the right child. Compare the combined sum with the current node value to determine if it should be counted. Return the total subtree sum (node value plus children sums) to the parent so the entire tree is processed in one traversal.
What is the best approach for Count Nodes Equal to Sum of Descendants?
The most efficient approach uses a postorder depth-first search. Each DFS call returns the sum of the subtree rooted at that node. By computing left and right subtree sums first, you can compare their total with the current node value. This processes each node once, giving O(n) time complexity and O(h) space from recursion.
Is Count Nodes Equal to Sum of Descendants asked at Google/Amazon/Meta?
Tree DFS problems that involve subtree sums and postorder traversal frequently appear in interviews at companies like Amazon, Google, and Meta. This specific pattern tests whether you can propagate values up a recursion stack while visiting nodes only once.
What data structure is used in Count Nodes Equal to Sum of Descendants?
The problem is based on a binary tree. The solution relies on depth-first search recursion to traverse the tree and compute subtree sums. No additional complex data structures are required beyond the recursion stack.
What is the time complexity of Count Nodes Equal to Sum of Descendants?
The optimal solution runs in O(n) time because each node in the binary tree is visited exactly once during the DFS traversal. The recursion stack uses O(h) space where h is the height of the tree. A naive brute-force approach that recomputes subtree sums for every node can take O(n^2) time.