LeetCode 1973 - Count Nodes Equal to Sum of Descendants

LeetCode Problem 1973

Difficulty: 🟡 Medium
Topics: Tree, Depth-First Search, Binary Tree

Solution

Problem Understanding

This problem asks us to analyze a binary tree and count how many nodes satisfy a specific property: the value of the node equals the sum of all its descendants. A descendant of a node is any node that lies in the subtree rooted at that node excluding the node itself. For example, if a node has two children, the sum of the descendants includes both children and all their respective subtrees. If a node has no children, the sum of its descendants is considered 0.

The input is the root of a binary tree. Each node contains an integer value, and we need to traverse the entire tree to find nodes satisfying the property. The output is a single integer representing the count of such nodes.

The constraints tell us the tree can be fairly large, with up to $10^5$ nodes, and all node values are non-negative integers between 0 and $10^5$. Because the tree can be large, any solution that visits nodes repeatedly in nested loops will likely be too slow. Edge cases include trees with only one node, trees where all nodes have value zero, or trees with large depths but small values, as these could expose integer overflow or recursive depth issues.

Approaches

Brute Force Approach

A naive approach is to compute the sum of descendants for each node individually. For each node, we would recursively traverse its subtree, sum all the descendant node values, and compare the sum to the node’s value. This approach works correctly because it explicitly calculates the property for every node, but it is inefficient. Each subtree sum computation could traverse up to $O(n)$ nodes, and if we repeat this for every node, the worst-case time complexity becomes $O(n^2)$, which is too slow for $n = 10^5$.

Optimal Approach

The key insight for an efficient solution is that we can compute subtree sums using a post-order depth-first traversal. In post-order traversal, we process the left subtree, then the right subtree, and then the node itself. This allows us to compute the sum of descendants for each node in a single pass: the sum of a node's descendants is the sum of the left and right subtrees. If we include this sum for the node itself, it becomes the total sum of the subtree, which can then propagate upward efficiently. Using this approach, each node is visited exactly once, giving $O(n)$ time complexity.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(h)	Recursively sum descendants for each node individually; h is the tree height.
Optimal	O(n)	O(h)	Post-order DFS calculates subtree sums in a single traversal.

Algorithm Walkthrough

1. Initialize a counter variable to keep track of nodes where the value equals the sum of descendants.
2. Define a recursive helper function that takes a node as input and returns the sum of the subtree rooted at that node.
3. In the helper function, if the node is None, return 0 because an empty subtree contributes nothing.
4. Recursively compute the sum of the left subtree and the right subtree.
5. Compute the sum of descendants as the sum of the left and right subtree sums.
6. Compare the node’s value with the sum of descendants. If they are equal, increment the counter.
7. Return the total sum of the subtree rooted at this node, which is the sum of descendants plus the node’s own value.
8. Start the recursion from the root node.
9. After the recursion finishes, return the counter as the final result.

Why it works: By performing post-order traversal, we ensure that for any given node, the sums of its left and right subtrees are already computed before checking the node. This guarantees that we compute descendant sums correctly for all nodes and only once, avoiding redundant computations.

Python 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:
        count = 0
        
        def dfs(node: Optional[TreeNode]) -> int:
            nonlocal count
            if not node:
                return 0
            left_sum = dfs(node.left)
            right_sum = dfs(node.right)
            descendants_sum = left_sum + right_sum
            if node.val == descendants_sum:
                count += 1
            return descendants_sum + node.val
        
        dfs(root)
        return count

The implementation defines a dfs helper function that returns the total sum of the subtree rooted at each node. The count variable is updated whenever a node’s value matches the sum of its descendants. Post-order traversal ensures left and right subtree sums are calculated before checking the node, exactly following the algorithm walkthrough.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func equalToDescendants(root *TreeNode) int {
    count := 0
    
    var dfs func(node *TreeNode) int
    dfs = func(node *TreeNode) int {
        if node == nil {
            return 0
        }
        leftSum := dfs(node.Left)
        rightSum := dfs(node.Right)
        descendantsSum := leftSum + rightSum
        if node.Val == descendantsSum {
            count++
        }
        return descendantsSum + node.Val
    }
    
    dfs(root)
    return count
}

In Go, nil is used instead of None. A closure is used to maintain the counter in the outer scope. The logic mirrors the Python solution exactly.

Worked Examples

Example 1: [10,3,4,2,1]

1. Compute left subtree sum for node 3: left=2, right=1, sum=3 → node.val = sum → count = 1
2. Compute right subtree sum for node 4: left=0, right=0, sum=0 → node.val ≠ sum → count = 1
3. Compute root 10: left sum=6, right sum=4, sum=10 → node.val = sum → count = 2

Final output = 2

Example 2: [2,3,null,2,null]

1. Node 2 (left child): left sum=2, right sum=0, node.val=3 ≠ 2 → count=0
2. Node 2 (root): left sum=5, right sum=0, node.val=2 ≠ 5 → count=0

Final output = 0

Example 3: [0]

1. Node 0: left sum=0, right sum=0 → node.val=sum → count=1

Final output = 1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each node is visited once in post-order DFS.
Space	O(h)	Recursion stack can grow to tree height, h.

The algorithm is efficient for large trees because each node is processed once, and no extra data structures are required except the recursion stack.

Test Cases

# Provided examples
assert Solution().equalToDescendants(TreeNode(10, TreeNode(3, TreeNode(2), TreeNode(1)), TreeNode(4))) == 2  # Example 1
assert Solution().equalToDescendants(TreeNode(2, TreeNode(3, TreeNode(2), None), None)) == 0  # Example 2
assert Solution().equalToDescendants(TreeNode(0)) == 1  # Example 3

# Edge cases
assert Solution().equalToDescendants(TreeNode(1)) == 1  # Single node tree
assert Solution().equalToDescendants(TreeNode(1, TreeNode(0), TreeNode(0))) == 1  # Root = sum of descendants
assert Solution().equalToDescendants(TreeNode(1, TreeNode(1), TreeNode(1))) == 2  # Leaves = 1, root ≠ sum

Test	Why
[10,3,4,2,1]	Tests multiple nodes matching property
[2,3,null,2,null]	Tests no nodes matching
[0]	Tests single node edge case
[1]	Single node, value=0 descendants
[1,0,0]	Root sum check
[1,1,1]	Leaf nodes match, root does not

Edge Cases

A tree with a single node is an important edge case because the sum of descendants is 0, and the node should be counted if its value is 0. The implementation handles this naturally as the DFS function returns 0 for null children.

A tree with all zero values tests whether the algorithm correctly counts every node. Because descendant sums will always match node values, each node should increment the count. The implementation correctly sums left and right children recursively, including zeros.

A highly unbalanced tree, such as a linked-list-shaped tree, tests the recursion depth. Python may hit recursion limits if the tree is extremely deep, while Go handles recursion efficiently. The algorithm still functions correctly because DFS correctly computes descendant sums along the single path.