Count Nodes Equal to Sum of Descendants - Solution & Explanation

Q: Is Count Nodes Equal to Sum of Descendants easy or hard?

The problem is generally classified as Medium. The core difficulty is recognizing that subtree sums should be computed with postorder traversal so each node is processed once. Once that insight is clear, the implementation becomes straightforward.

Q: Count Nodes Equal to Sum of Descendants Python/Java solution

Implement a recursive DFS function that returns the subtree sum. For each node, compute leftSum and rightSum, compare their total with node.val, and increment a counter if they match. The same logic works in Python, Java, C++, and Go with O(n) time complexity.

Q: How to solve Count Nodes Equal to Sum of Descendants in O(n)?

Use a postorder DFS that returns the sum of each subtree. First compute the sum from the left child, then the right child. Compare the combined sum with the current node value to determine if it should be counted. Return the total subtree sum (node value plus children sums) to the parent so the entire tree is processed in one traversal.

Q: What is the best approach for Count Nodes Equal to Sum of Descendants?

The most efficient approach uses a postorder depth-first search. Each DFS call returns the sum of the subtree rooted at that node. By computing left and right subtree sums first, you can compare their total with the current node value. This processes each node once, giving O(n) time complexity and O(h) space from recursion.

Q: Is Count Nodes Equal to Sum of Descendants asked at Google/Amazon/Meta?

Tree DFS problems that involve subtree sums and postorder traversal frequently appear in interviews at companies like Amazon, Google, and Meta. This specific pattern tests whether you can propagate values up a recursion stack while visiting nodes only once.

Q: What data structure is used in Count Nodes Equal to Sum of Descendants?

The problem is based on a binary tree. The solution relies on depth-first search recursion to traverse the tree and compute subtree sums. No additional complex data structures are required beyond the recursion stack.

Q: What is the time complexity of Count Nodes Equal to Sum of Descendants?

The optimal solution runs in O(n) time because each node in the binary tree is visited exactly once during the DFS traversal. The recursion stack uses O(h) space where h is the height of the tree. A naive brute-force approach that recomputes subtree sums for every node can take O(n^2) time.

MediumPremiumFree on FleetCodeTree Depth-First Search Binary Tree5 min readAsked at: Meta

Practice this problem

Problem Statement

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.

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, 10⁵].
0 <= Node.val <= 10⁵

Approach Overview

Problem Overview: Given a binary tree, count how many nodes have a value equal to the sum of all their descendant nodes. Descendants include every node in the subtree excluding the node itself. The challenge is efficiently computing subtree sums while visiting each node.

Approach 1: Recompute Subtree Sum for Every Node (Brute Force) (Time: O(n²), Space: O(h))

Traverse every node in the tree and compute the sum of its descendants using a separate recursive function. For each node, run a DFS that sums all nodes in its left and right subtrees, then compare that sum with the current node value. If they match, increment the counter. This approach repeatedly recalculates subtree sums, causing the same nodes to be visited many times.

The method uses a standard tree traversal and a helper function to compute subtree totals. On a skewed tree, each node may trigger a traversal of nearly the entire remaining tree. That leads to O(n^2) time in the worst case. Space usage is O(h) from the recursion stack, where h is the tree height.

Approach 2: Postorder DFS with Subtree Sum Propagation (Optimal) (Time: O(n), Space: O(h))

The efficient solution computes subtree sums during a single traversal using postorder DFS. Visit the left subtree, then the right subtree, then process the current node. Each recursive call returns the total sum of the subtree rooted at that node.

At each node, combine the sums returned from the left and right children. That value represents the sum of all descendants. Compare it with the node's value and increment the result if they match. Then return node.val + leftSum + rightSum so the parent can continue building the total.

This technique ensures each node contributes to the subtree sum exactly once. The algorithm relies on depth-first search over a binary tree. Because each node is processed a single time, the total runtime is O(n). Memory usage comes only from recursion depth, which is O(h).

Recommended for interviews: Interviewers expect the postorder DFS approach. It demonstrates that you recognize subtree computations should flow from children to parent. Starting with the brute force method shows understanding of the problem, but optimizing it to a single traversal proves you know how to eliminate repeated work in tree problems.

Solution

Code

Python Java C++Go

Python

Java

C++

Try this approach in the editor →

Detailed Complexity Analysis

Approach	Time	Space	When to Use
Recompute Subtree Sum for Each Node (Brute Force)	O(n^2)	O(h)	Useful for understanding the problem before optimizing or when the tree is very small
Postorder DFS with Subtree Sum Propagation	O(n)	O(h)	Best general solution; processes each node once and avoids repeated subtree calculations

Video Solution

1973. Count Nodes Equal to Sum of Descendants - Week 5/5 Leetcode February Challenge • Programming Live with Larry • 152 views views

Watch 4 more video solutions →

Frequently Asked Questions

Is Count Nodes Equal to Sum of Descendants easy or hard?

The problem is generally classified as Medium. The core difficulty is recognizing that subtree sums should be computed with postorder traversal so each node is processed once. Once that insight is clear, the implementation becomes straightforward.

Count Nodes Equal to Sum of Descendants Python/Java solution

Implement a recursive DFS function that returns the subtree sum. For each node, compute leftSum and rightSum, compare their total with node.val, and increment a counter if they match. The same logic works in Python, Java, C++, and Go with O(n) time complexity.

How to solve Count Nodes Equal to Sum of Descendants in O(n)?

Use a postorder DFS that returns the sum of each subtree. First compute the sum from the left child, then the right child. Compare the combined sum with the current node value to determine if it should be counted. Return the total subtree sum (node value plus children sums) to the parent so the entire tree is processed in one traversal.

What is the best approach for Count Nodes Equal to Sum of Descendants?

The most efficient approach uses a postorder depth-first search. Each DFS call returns the sum of the subtree rooted at that node. By computing left and right subtree sums first, you can compare their total with the current node value. This processes each node once, giving O(n) time complexity and O(h) space from recursion.

Is Count Nodes Equal to Sum of Descendants asked at Google/Amazon/Meta?

Tree DFS problems that involve subtree sums and postorder traversal frequently appear in interviews at companies like Amazon, Google, and Meta. This specific pattern tests whether you can propagate values up a recursion stack while visiting nodes only once.

What data structure is used in Count Nodes Equal to Sum of Descendants?

The problem is based on a binary tree. The solution relies on depth-first search recursion to traverse the tree and compute subtree sums. No additional complex data structures are required beyond the recursion stack.

What is the time complexity of Count Nodes Equal to Sum of Descendants?

The optimal solution runs in O(n) time because each node in the binary tree is visited exactly once during the DFS traversal. The recursion stack uses O(h) space where h is the height of the tree. A naive brute-force approach that recomputes subtree sums for every node can take O(n^2) time.

Ready to solve this problem?

Practice Count Nodes Equal to Sum of Descendants with our built-in code editor and test cases.

Practice on FleetCode

Count Nodes Equal to Average of Subtree

Maximum Average Subtree

Problem Info

DifficultyMedium

Acceptance77.4%

Approaches1

Reading time5 min

Asked at