Distribute Coins in Binary Tree
Medium · Trees · Tree · Depth-First Search · Binary Tree
Problem
You are given the root of a binary tree with n nodes, where node.val is the number of coins on that node. There are exactly n coins in the whole tree.
In one move you take one coin and carry it across one edge, from a parent to a child or from a child to its parent.
Return the fewest moves that leave every node with exactly one coin.
Examples
Input: root = [0,3,0] Output: 3
The left child sends one coin up to the root and another through the root to the right child: 1 + 2 = 3 moves.
Input: root = [1,0,0,null,3] Output: 4
The node holding 3 sends two coins up to its parent (2 moves); one stays and the other goes on through the root to the root's right child (2 more moves).
Constraints
- The number of nodes is n, with 1 <= n <= 100
- 0 <= Node.val <= n
- The values add up to n
Approaches
- Recount every subtree for its edge — time O(n²), space O(h)
Follow-up
What if each node wanted its own number of coins, and nodes could have any number of children? The same edge argument holds with excess = coins - total need for every subtree; see the use case "Any tree, any target per node".
Related problems
Start free on Cariara · Coding problems · System design studio
