Count Nodes Equal to Sum of Descendants
Medium · Trees · Tree · Depth-First Search · Binary Tree
Problem
Given the root of a binary tree, return how many nodes have a value equal to the sum of the values of their descendants.
The descendants of a node are all nodes below it on paths toward the leaves (children, grandchildren, and so on). A node with no descendants has a descendant sum of 0.
Examples
Input: root = [12,5,2,3,2] Output: 2
5 equals 3 + 2, and 12 equals 5 + 2 + 3 + 2; the leaves are not 0, so they do not count.
Input: root = [0,0] Output: 2
The leaf 0 has descendant sum 0, and so does the root.
Input: root = [1,2,3] Output: 0
The root is 1 but its descendants add up to 5, and the leaves are not 0.
Constraints
- The number of nodes is in the range [1, 10^4]
- 0 <= Node.val <= 10^5
Approaches
- Baseline: sum the descendants of every node — time O(n^2), space O(n)
Follow-up
One bottom-up pass answers every "whole subtree" question at once. The use cases look one level down (only the children) and upward (the ancestors), where the sums travel from the root instead.
Related problems
Start free on Cariara · Coding problems · System design studio
