Count Nodes Equal to Sum of Descendants - Practice Coding Problems

Count Nodes Equal to Sum of Descendants - 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.

Input & Output

Example 1 — Basic Tree

$ Input: root = [10,3,4,2,1]

› Output: 2

💡 Note: Node 10: descendants are [3,4,2,1], sum = 10 (matches). Node 3: descendants are [2,1], sum = 3 (matches). Node 4 has no descendants, sum = 0 ≠ 4.

Example 2 — Single Node

$ Input: root = [2]

› Output: 1

💡 Note: Single node with no descendants. Sum of descendants = 0, but node value = 2, so it doesn't match. Wait, the node has no descendants so sum = 0, and 2 ≠ 0, so result is 0.

Example 3 — No Matches

$ Input: root = [0]

› Output: 1

💡 Note: Single node with value 0. It has no descendants, so sum of descendants = 0. Since 0 = 0, this node matches.

Constraints

The number of nodes in the tree is in the range [1, 10⁵]
-10⁵ ≤ Node.val ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Binary tree with node values

Calculate Descendant Sums

For each node, find sum of all descendants

Count Matches

Count nodes where value equals descendant sum

Key Takeaway

🎯 Key Insight: Use post-order DFS to calculate subtree sums bottom-up in one pass

Asked in

G Google 15 A Amazon 12

The key insight is to use post-order DFS traversal to calculate subtree sums efficiently. Best approach uses single-pass DFS where we calculate descendant sums bottom-up and count matches during traversal. Time: O(n), Space: O(h)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized DFS - Single Pass	O(n)	O(h)	Use post-order DFS to calculate subtree sums in one pass while counting matches
Brute Force - Calculate Sum for Each Node	O(n²)	O(h)	For each node, recursively calculate the sum of all descendants separately

Optimized DFS - Single Pass — Algorithm Steps

Use post-order DFS traversal
Calculate subtree sum at each node
Check if node value equals descendant sum
Return subtree sum to parent

Visualization

Tap to expand

Step-by-Step Walkthrough

Post-order Traversal

Visit children before processing current node

Calculate & Compare

Get descendant sum and compare with node value

Return Sum

Return total subtree sum to parent

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

int result = 0;

struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int dfs(struct TreeNode* node) {
    if (!node) return 0;
    
    // Get subtree sums from children
    int leftSum = dfs(node->left);
    int rightSum = dfs(node->right);
    
    // Total descendant sum for current node
    int descendantSum = leftSum + rightSum;
    
    // Check if current node value equals descendant sum
    if (node->val == descendantSum) {
        result++;
    }
    
    // Return total sum of subtree rooted at current node
    return node->val + descendantSum;
}

int solution(struct TreeNode* root) {
    if (!root) return 0;
    result = 0;
    dfs(root);
    return result;
}

int main() {
    // For simplicity, assume a small test case
    struct TreeNode* root = createNode(10);
    root->left = createNode(3);
    root->right = createNode(4);
    root->left->left = createNode(2);
    root->left->right = createNode(1);
    
    int ans = solution(root);
    printf("%d\n", ans);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Visit each node exactly once in the tree traversal

✓ Linear Growth

Space Complexity

O(h)

Recursion stack depth equals tree height h

✓ Linear Space

23.1K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized DFS - Single Pass — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler