Watch 5 video solutions for Count Nodes Equal to Sum of Descendants, a medium level problem involving Tree, Depth-First Search, Binary Tree. This walkthrough by Programming Live with Larry has 146 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
[1, 105].0 <= Node.val <= 105Problem 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.
| 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 |