Count Nodes Equal to Sum of Descendants

Problem Statement

In this challenge, we are provided with the root of a binary tree and our task is to determine the number of nodes where the node's own value equals the sum of the values of all its descendants. To be clear, a descendant of a node x in this context is defined as any node that lies on the path from node x down to any leaf node. It is important to note that if a node does not have any descendants, the sum of its descendants is considered to be 0. This setup asks for how many such nodes in a given tree satisfy this particular condition.

Examples

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 and Intuition

To solve this problem, one can adopt a depth-first search (DFS) approach that traverses through the tree and calculates the sum of the descendant nodes for each node. While doing so, it also checks if the condition of the node's value being equal to this sum is met. Here's a step-by-step breakdown:

1. Begin by establishing a recursive function, often termed dfs or similar, that will take in a node of the tree as its parameter.
2. For each node, if it's null (indicative of reaching past a leaf), return a sum of 0.
3. Recursively call this function on the left child and right child of the current node to get the sum of values from both subtrees.
4. Add the two sums derived from the left and right subtree calls. This sum represents the total descendant sum for the current node.
5. Check if the current node's value equals this sum. If it does, increment a global or external counter that tracks the number of such nodes.
6. Finally, update the return value of the dfs function to include the current node's value plus the sum of its descendants, as this total sum is passed up the call stack to the parent node.

The main idea is recursively to accumulate descendant sums up the tree while also comparing each node's value to its descendant sum. This approach implicitly handles edge cases such as:

• Nodes with no children where the descendant sum should be 0.
• Trees with just one node, which technically meets the condition trivially as its own value is necessarily equal to its descendant sum (which is 0).

When implemented efficiently, this solution will traverse each node a single time, resulting in a time complexity of O(n), where n is the number of nodes in the tree. The recursive nature of the DFS approach makes the space complexity O(h), where h is the height of the tree, due to the stack space used by recursive calls.

Solutions

class Solution {
public:
    int nodeCount;
    
    long recursiveNodeSum(TreeNode* node) {
        if (node == nullptr) {
            return 0;
        }
        
        long sumLeft = recursiveNodeSum(node->left);
        long sumRight = recursiveNodeSum(node->right);
        
        if (node->val == sumLeft + sumRight) {
            nodeCount++;
        }
        
        return sumLeft + sumRight + node->val;
    }
    
    int nodesEqualToSumDescendants(TreeNode* node) {
        recursiveNodeSum(node);
        return nodeCount;
    }
};

class Solution {
    int totalEqual;

    private long sumNodes(TreeNode node) {
        if (node == null) {
            return 0;
        }

        long sumLeft = sumNodes(node.left);
        long sumRight = sumNodes(node.right);

        if (node.val == sumLeft + sumRight) {
            totalEqual++;
        }

        return sumLeft + sumRight + node.val;
    }

    public int countEqualDescendants(TreeNode root) {
        sumNodes(root);
        return totalEqual;
    }
}