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 thesum 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.

Examples

Example 1:

graph TD;
A(10):::blue --- B(3):::blue
A --- C(4)
B --- D(2)
B --- E(1)


classDef hidden display:none
classDef blue fill:#2196f3,stroke:#1565c0,color:#fff;

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:

graph TD;
A(2) --- B(3)
A ~~~ N1:::hidden
B --- C(2)
B ~~~ N2:::hidden

classDef hidden display:none

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:

graph TD;
A(0):::blue
classDef blue fill:#2196f3,stroke:#1565c0,color:#fff;

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 <= 10^5

Solution

Method 1 – Postorder DFS with Subtree Sum

Intuition

For each node, we need to know the sum of all its descendants. We can use postorder DFS to compute the sum for every node efficiently. If a node's value equals the sum of its descendants, we increment the answer.

Approach

1. Traverse the tree in postorder (left, right, root).
2. For each node, recursively get the sum of its left and right subtrees.
3. The sum of descendants is the sum of left and right subtrees.
4. If the node's value equals the sum of its descendants, increment the answer.
5. Return the answer after traversing the whole tree.

Code

C++

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    int ans = 0;
    int dfs(TreeNode* node) {
        if (!node) return 0;
        int ls = dfs(node->left);
        int rs = dfs(node->right);
        int sum = ls + rs;
        if (node->val == sum) ans++;
        return sum + node->val;
    }
    int equalToDescendants(TreeNode* root) {
        ans = 0;
        dfs(root);
        return ans;
    }
};

Go

type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode
}

func EqualToDescendants(root *TreeNode) int {
    var ans int
    var dfs func(*TreeNode) int
    dfs = func(node *TreeNode) int {
        if node == nil {
            return 0
        }
        ls := dfs(node.Left)
        rs := dfs(node.Right)
        sum := ls + rs
        if node.Val == sum {
            ans++
        }
        return sum + node.Val
    }
    dfs(root)
    return ans
}

Java

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}
class Solution {
    int ans = 0;
    private int dfs(TreeNode node) {
        if (node == null) return 0;
        int ls = dfs(node.left), rs = dfs(node.right);
        int sum = ls + rs;
        if (node.val == sum) ans++;
        return sum + node.val;
    }
    public int equalToDescendants(TreeNode root) {
        ans = 0;
        dfs(root);
        return ans;
    }
}

Kotlin

data class TreeNode(var `val`: Int, var left: TreeNode? = null, var right: TreeNode? = null)
class Solution {
    var ans = 0
    fun equalToDescendants(root: TreeNode?): Int {
        ans = 0
        fun dfs(node: TreeNode?): Int {
            if (node == null) return 0
            val ls = dfs(node.left)
            val rs = dfs(node.right)
            val sum = ls + rs
            if (node.`val` == sum) ans++
            return sum + node.`val`
        }
        dfs(root)
        return ans
    }
}

Python

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: TreeNode) -> int:
        self.ans = 0
        def dfs(node: TreeNode) -> int:
            if not node:
                return 0
            ls = dfs(node.left)
            rs = dfs(node.right)
            s = ls + rs
            if node.val == s:
                self.ans += 1
            return s + node.val
        dfs(root)
        return self.ans

Rust

pub struct TreeNode {
    pub val: i32,
    pub left: Option<Box<TreeNode>>,
    pub right: Option<Box<TreeNode>>,
}

impl Solution {
    pub fn equal_to_descendants(root: Option<Box<TreeNode>>) -> i32 {
        fn dfs(node: &Option<Box<TreeNode>>, ans: &mut i32) -> i32 {
            if let Some(n) = node {
                let ls = dfs(&n.left, ans);
                let rs = dfs(&n.right, ans);
                let sum = ls + rs;
                if n.val == sum { *ans += 1; }
                sum + n.val
            } else {
                0
            }
        }
        let mut ans = 0;
        dfs(&root, &mut ans);
        ans
    }
}

TypeScript

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = val ?? 0;
        this.left = left ?? null;
        this.right = right ?? null;
    }
}
class Solution {
    equalToDescendants(root: TreeNode | null): number {
        let ans = 0;
        function dfs(node: TreeNode | null): number {
            if (!node) return 0;
            const ls = dfs(node.left);
            const rs = dfs(node.right);
            const sum = ls + rs;
            if (node.val === sum) ans++;
            return sum + node.val;
        }
        dfs(root);
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(n), where n is the number of nodes, since we visit each node once.
• 🧺 Space complexity: O(h), where h is the height of the tree, due to recursion stack.