Distribute Coins in Binary Tree
Last Updated: March 29, 2026
Understanding the Problem
We have a binary tree where each node holds some number of coins, and the total coins across the entire tree equals the number of nodes. Our goal is to redistribute these coins so that every node ends up with exactly one coin, and we want to do it in the fewest moves possible. Each move transfers one coin between adjacent nodes (parent-child).
The key insight is thinking about this from the edges' perspective rather than the nodes'. Every edge in the tree acts as a highway between a subtree and the rest of the tree. If a subtree has too many coins, the excess must flow out through that edge. If a subtree has too few coins, coins must flow in through that edge. The number of moves across an edge equals the absolute value of the "excess" in the subtree below it. The total moves is the sum of these absolute values across all edges.
Key Constraints:
1 <= n <= 100- The tree is very small. Even O(n^3) would run instantly. The challenge here is the algorithmic insight, not performance.0 <= Node.val <= n- Nodes can have zero coins (they need one) or many coins (they have excess). This asymmetry is what creates the redistribution problem.Sum of all Node.val is n- Total coins equals total nodes, so a valid redistribution always exists. We never need to create or destroy coins.
Approach 1: Brute Force (BFS Simulation)
Intuition
The most straightforward way to think about this: simulate the redistribution. Find nodes that need coins (val = 0) and nodes that have extra coins (val > 1), then move coins one at a time along the shortest path between them. We use BFS to find the shortest path between donor and receiver nodes, and each step along that path is one move.
This approach is simple but inefficient because we are computing paths individually for every coin transfer, and there could be many such transfers.
Algorithm
- Build a parent map so we can traverse the tree in both directions (parent-to-child and child-to-parent).
- Find a node with excess coins (val > 1).
- Use BFS to find the nearest node that needs a coin (val = 0).
- Compute the distance between them (each edge = one move) and add it to the total.
- Transfer one coin: decrement the donor, increment the receiver.
- Repeat until every node has exactly one coin.
Example Walkthrough
Input:
The root has 3 coins and each child has 0. We find the root has excess, BFS to the left child (distance 1, 1 move), transfer a coin. Then BFS to the right child (distance 1, 1 move), transfer another coin. Total: 2 moves.
Code
- Time Complexity: O(n^3) worst case. For each excess coin, we run a BFS (O(n)) to find the nearest receiver and another BFS (O(n)) to compute the distance. With up to O(n) excess coins, this gives O(n^3).
- Space Complexity: O(n). The parent map, node list, and BFS visited sets each use O(n) space.
This approach handles coins one at a time. Coins from the same subtree often flow through the same edges, but we recompute those paths separately for each coin. What if we computed the net flow across each edge in a single pass?
Approach 2: Post-Order DFS (Subtree Excess)
Intuition
Here is the big insight: stop thinking about individual coins and start thinking about edges. Every edge in the tree sits between a subtree and the rest of the tree. If a subtree has more coins than it has nodes, the excess must flow out through the connecting edge to the parent. If it has fewer coins than nodes, the deficit must flow in through that same edge.
For any subtree rooted at a node, define its "excess" as (total coins in subtree) - (number of nodes in subtree). A positive excess means coins flow upward through the edge. A negative excess means coins flow downward. Either way, the number of moves across that edge is |excess|. The total answer is the sum of |excess| for every node.
We compute excess bottom-up with post-order DFS. After visiting both children, a node knows the excess of its left subtree and right subtree. The node's own excess is: node.val - 1 + leftExcess + rightExcess. The -1 accounts for the coin this node keeps for itself.
The beauty of this approach is that it decomposes a global problem into local decisions. Instead of tracking where each coin goes, we observe that every coin that crosses an edge contributes exactly one move. The net flow across an edge is completely determined by the subtree below it: if the subtree has excess coins, they must leave; if it has a deficit, coins must enter.
By computing excess bottom-up, each node aggregates the needs of its entire subtree into a single number. The absolute value of the left child's excess tells us how many coins cross the left edge, and similarly for the right. This counting is exact because coins can only enter or leave a subtree through its one connecting edge to the parent. The final excess at the root is always 0, confirming our accounting is consistent.
Algorithm
- Run a post-order DFS starting from the root.
- For null nodes, return an excess of 0 (no coins, no nodes).
- At each node, recursively compute the excess of the left and right subtrees.
- Compute this node's excess as:
node.val - 1 + leftExcess + rightExcess. - Add
|leftExcess| + |rightExcess|to the global move counter (these represent the coin flow on the left and right edges). - Return this node's excess to its parent.
Example Walkthrough
Code
- Time Complexity: O(n). We visit each node exactly once in the post-order DFS. Each visit does O(1) work: two recursive calls, a couple of additions, and an absolute value computation.
- Space Complexity: O(h) where h is the height of the tree. The recursion stack holds at most h frames. In the worst case (a completely skewed tree), h = n. For a balanced tree, h = log(n).