Count Nodes Equal To Sum Of Descendants
01 · Problem
Given the root of a binary tree, return the number of nodes whose value is equal to the sum of the values of all their descendants.
A descendant of a node is any node reached by moving down from it through child links (children, grandchildren, and so on); the node itself is not its own descendant. A node with no descendants has a descendant sum of 0, so a leaf counts only if its value is 0. The tree is given in level-order form, with null marking missing children.
02 · Examples
root = [10,3,4,2,1]
2
Node 10's descendants sum to 3 + 4 + 2 + 1 = 10, and node 3's descendants sum to 2 + 1 = 3. No other node qualifies.
root = [2,3,null,2]
0
Node 2 (root) has descendant sum 5, node 3 has 2, and the leaf 2 has 0; none match.
root = [0]
1
The single leaf has value 0, which equals its empty descendant sum of 0.
03 · Constraints
- 01The number of nodes in the tree is in the range [1, 105].
- 020 <= Node.val <= 105
- 03A leaf has a descendant sum of 0.
- 04Descendant sums can exceed the 32-bit range, so accumulate them in 64-bit integers.
04 · Optimal complexity
- Time
- O(n)
- Space
- O(h)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.