Children Sum Property in Binary Tree
MediumPush values down, then fix on the way up
Problem
Change node values (only increases allowed) so every node equals the sum of its children (children-sum property).
Check every non-leaf equals the sum of its children's values, recursively.
The idea
On the way down, raise any child smaller than its parent to the parent's value — increasing is allowed, so this is always safe. On the way back up, set each node to the sum of its children, which now cannot be too small.
The trick
- Downward pass raises children; upward pass recomputes parents.
- Only increases are permitted, which is why the downward pass is legal.
- Leaves are left as they are.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — [35,20,15] Values: 35, 20, 15.
1top-down: if parent<childrenSum push parent value into children2bottom-up: set parent = children sumInput
- array
- [35, 20, 15]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- tree = [10,4,6,null,null,null,null]
- Output:
- true
- Explanation:
- 10 = 4 + 6, so it holds.
Example 2
- Input:
- tree = [10,3,6]
- Output:
- false
- Explanation:
- 10 != 3 + 6 → false.
Example 3
- Input:
- tree = [1]
- Output:
- true
- Explanation:
- A leaf trivially satisfies it.
Practice this problem:GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.