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.

Description Hints 2 Solution Video 4:44

1973. Count Nodes Equal to Sum of Descendants

Medium77.4% acceptance1 companyPremium elsewhere, free here

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⁵

Asked at 1 company

Topics

Hints open one at a time

Hint 1

Can we reuse previously calculated information?

Hint 2

How can we calculate the sum of the current subtree using the sum of the child's subtree?

4:44

Still stuck?Read the written solution, or watch a walkthrough.

Open solution