Problem Description

You are given the root of a binary tree. Your task is to count how many nodes in the tree have a value that equals the sum of all their descendant nodes' values.

A descendant of a node is any node that can be reached by traveling downward from that node (following the path toward the leaves). This includes the node's children, grandchildren, and so on, all the way to the leaf nodes.

For nodes that have no descendants (leaf nodes), the sum of descendants is considered to be 0.

The solution uses a depth-first search (DFS) approach that traverses the tree from bottom to top. For each node, it:

1. Recursively calculates the sum of all values in the left subtree
2. Recursively calculates the sum of all values in the right subtree
3. Checks if the sum of these two subtree values equals the current node's value
4. If they are equal, increments the counter
5. Returns the total sum of the current subtree (current node value + left subtree sum + right subtree sum) for use by parent nodes

For example, if a node has value 10 and its left subtree nodes sum to 4 and right subtree nodes sum to 6, then 4 + 6 = 10 equals the node's value, so this node would be counted. The function would return 10 + 4 + 6 = 20 as the sum for this subtree.

The nonlocal keyword is used to modify the ans variable from the outer scope, allowing the nested function to update the count of valid nodes as it traverses the tree.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The problem involves a binary tree, which is a special type of graph with nodes connected by edges (parent-child relationships).

Is it a tree?

• Yes: The problem explicitly states we're working with a binary tree structure where we have a root node and each node can have at most two children.

DFS

• We arrive at DFS: Since we're dealing with a tree structure, the flowchart directly leads us to use Depth-First Search (DFS).

Why DFS is the right choice:

• We need to calculate the sum of all descendant nodes for each node in the tree
• This requires visiting child nodes first before we can determine if a parent node's value equals the sum of its descendants
• DFS with post-order traversal (process children before parent) is perfect for this bottom-up calculation
• As we return from recursive calls, we can accumulate the sums from subtrees and check the condition at each node

Conclusion: The flowchart correctly identifies that for a tree-based problem requiring information from descendants to make decisions about ancestors, DFS is the optimal approach. The recursive nature of DFS allows us to naturally compute subtree sums while traversing back up the tree.

Intuition

When we need to check if a node's value equals the sum of all its descendants, we face a key challenge: we can't know the sum of descendants until we've visited all of them. This naturally suggests a bottom-up approach where we process leaf nodes first and work our way back to the root.

Think about it this way: if we're standing at a node, we need to know:

1. The sum of all values in the left subtree (all left descendants)
2. The sum of all values in the right subtree (all right descendants)

Only after obtaining these two pieces of information can we check if left_sum + right_sum == node.val.

This points us toward a post-order traversal pattern where we:

• First recursively process the left child
• Then recursively process the right child
• Finally process the current node

The beauty of this recursive approach is that each recursive call can return the total sum of its subtree. When we're at a node, the recursive calls to its children give us exactly what we need - the sum of all descendants in each subtree.

For example, when processing a node with value 10:

• The left recursive call returns 4 (sum of all left descendants)
• The right recursive call returns 6 (sum of all right descendants)
• We check if 4 + 6 == 10 and increment our counter if true
• We return 10 + 4 + 6 = 20 to our parent, representing the total sum of this entire subtree

This way, each node gets the information it needs from its children, makes its decision, and passes useful information up to its parent - a classic recursive pattern that elegantly solves the problem in a single tree traversal.

Learn more about Tree, Depth-First Search and Binary Tree patterns.

Solution Approach

The implementation uses a recursive DFS function that processes the tree in a post-order manner. Let's walk through the key components:

Main Structure:

• We define a nested dfs function that will traverse the tree and return the sum of each subtree
• We use a nonlocal variable ans to keep track of the count of valid nodes across all recursive calls

Base Case:

if root is None:
    return 0

When we encounter a None node (empty subtree), we return 0 as the sum, which naturally handles leaf nodes whose children are None.

Recursive Processing:

l, r = dfs(root.left), dfs(root.right)

We recursively calculate:

• l: the sum of all nodes in the left subtree
• r: the sum of all nodes in the right subtree

These recursive calls happen first (before processing the current node), ensuring we have the descendant information we need.

Checking the Condition:

if l + r == root.val:
    nonlocal ans
    ans += 1

After obtaining the sums from both subtrees, we check if their sum equals the current node's value. If it does, we increment our counter. The nonlocal keyword allows us to modify the ans variable from the outer scope.

Returning the Subtree Sum:

return root.val + l + r

This is crucial - we return the total sum of the current subtree (current node's value plus both subtree sums). This returned value becomes the l or r value for the parent node's calculation.

Time and Space Complexity:

• Time: O(n) where n is the number of nodes, as we visit each node exactly once
• Space: O(h) where h is the height of the tree, representing the recursion stack depth (worst case O(n) for a skewed tree)

The elegance of this solution lies in how it combines the traversal with the computation - each recursive call serves dual purposes: checking the condition for the current node and providing necessary information to parent nodes.

Example Walkthrough

Let's walk through a concrete example to see how the algorithm works. Consider this binary tree:

        12
       /  \
      3    9
     / \    \
    1   2    5

We want to count nodes whose value equals the sum of all their descendants.

Step-by-step execution:

1. Start at root (12): The DFS begins but immediately recurses to process children first.

2. Process left subtree of 12 (node 3):

   • First recurse to node 3's children
   • Node 1 (leaf):
     • Left child: None → returns 0
     • Right child: None → returns 0
     • Check: 0 + 0 = 0, but node.val = 1 (not equal, don't count)
     • Returns: 1 + 0 + 0 = 1
   • Node 2 (leaf):
     • Left child: None → returns 0
     • Right child: None → returns 0
     • Check: 0 + 0 = 0, but node.val = 2 (not equal, don't count)
     • Returns: 2 + 0 + 0 = 2
   • Back to Node 3:
     • Left subtree sum: 1 (from node 1)
     • Right subtree sum: 2 (from node 2)
     • Check: 1 + 2 = 3, and node.val = 3 ✓ (equal, count it!)
     • ans = 1
     • Returns: 3 + 1 + 2 = 6

3. Process right subtree of 12 (node 9):

   • First recurse to node 9's children
   • Node 5 (leaf):
     • Left child: None → returns 0
     • Right child: None → returns 0
     • Check: 0 + 0 = 0, but node.val = 5 (not equal, don't count)
     • Returns: 5 + 0 + 0 = 5
   • Back to Node 9:
     • Left subtree sum: 0 (no left child)
     • Right subtree sum: 5 (from node 5)
     • Check: 0 + 5 = 5, but node.val = 9 (not equal, don't count)
     • Returns: 9 + 0 + 5 = 14

4. Finally process root (12):

   • Left subtree sum: 6 (sum of nodes 3, 1, 2)
   • Right subtree sum: 14 (sum of nodes 9, 5)
   • Check: 6 + 14 = 20, but node.val = 12 (not equal, don't count)
   • Returns: 12 + 6 + 14 = 32 (total tree sum)

Result: ans = 1 (only node 3 satisfies the condition)

The key insight is how each recursive call returns the sum of its entire subtree, which becomes exactly the "sum of descendants" needed by the parent node. This bottom-up information flow allows us to check each node's condition in a single traversal.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the number of nodes in the binary tree. The algorithm performs a depth-first search (DFS) traversal that visits each node exactly once. At each node, it performs constant time operations (comparison and addition), so the overall time complexity is linear with respect to the number of nodes.

Space Complexity: O(h) where h is the height of the binary tree. The space complexity is determined by the recursive call stack during the DFS traversal. In the worst case (a skewed tree), the height could be O(n), making the space complexity O(n). In the best case (a balanced tree), the height would be O(log n), making the space complexity O(log n). The additional space used for the ans variable is O(1) and doesn't affect the overall space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding the Problem Definition

A common mistake is confusing "sum of descendants" with "sum of all nodes in the subtree including the node itself." The problem specifically asks for the sum of descendants only, which excludes the current node's value.

Incorrect interpretation:

# WRONG: Including the node itself in the comparison
def dfs(node):
    if node is None:
        return 0
  
    left_sum = dfs(node.left)
    right_sum = dfs(node.right)
    subtree_sum = node.val + left_sum + right_sum
  
    # This compares against the entire subtree sum, not just descendants
    if subtree_sum == node.val:  # This would only be true when descendants sum to 0
        nonlocal result_count
        result_count += 1
  
    return subtree_sum

Correct approach:

# RIGHT: Comparing node value with sum of descendants only
if left_sum + right_sum == node.val:  # Descendants sum excludes current node
    nonlocal result_count
    result_count += 1

2. Forgetting to Declare nonlocal for the Counter Variable

Without the nonlocal declaration, Python treats result_count as a local variable when you try to modify it, leading to an UnboundLocalError.

Incorrect code:

def equalToDescendants(self, root):
    result_count = 0
  
    def dfs(node):
        if node is None:
            return 0
      
        left_sum = dfs(node.left)
        right_sum = dfs(node.right)
      
        if left_sum + right_sum == node.val:
            result_count += 1  # ERROR: UnboundLocalError
      
        return node.val + left_sum + right_sum
  
    dfs(root)
    return result_count

Solution: Always declare nonlocal before modifying an outer scope variable:

if left_sum + right_sum == node.val:
    nonlocal result_count  # Declare before modifying
    result_count += 1

3. Incorrect Return Value from DFS Function

Some might mistakenly return only the count or forget to include all components in the sum, breaking the logic for parent nodes.

Common mistakes:

# WRONG: Returning the count instead of sum
def dfs(node):
    if node is None:
        return 0
  
    left_sum = dfs(node.left)
    right_sum = dfs(node.right)
  
    if left_sum + right_sum == node.val:
        return 1  # WRONG: Should return sum, not count
    return 0

# WRONG: Forgetting to include node's own value in return
def dfs(node):
    if node is None:
        return 0
  
    left_sum = dfs(node.left)
    right_sum = dfs(node.right)
  
    if left_sum + right_sum == node.val:
        nonlocal result_count
        result_count += 1
  
    return left_sum + right_sum  # WRONG: Missing node.val

Correct return:

return node.val + left_sum + right_sum  # Include all three components

4. Edge Case: Single Node Tree

While the provided solution handles this correctly, it's worth noting that a single node (root with no children) should be counted if its value equals 0 (since the sum of its descendants is 0).

Test case to verify:

# Tree with single node having value 0
#     0
# Expected output: 1 (since sum of descendants = 0)

# Tree with single node having value 5
#     5
# Expected output: 0 (since sum of descendants = 0, not 5)

The solution correctly handles this because leaf nodes get left_sum = 0 and right_sum = 0 from their null children, so the comparison 0 + 0 == node.val works as expected.