Distribute Coins in Binary Tree
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 problem becomes simpler when viewed from the edges rather than the nodes. Every edge connects a subtree to the rest of the tree. If a subtree holds more coins than it has nodes, the surplus must flow out through that edge toward the parent. If it holds fewer, coins must flow in through the same edge. The number of moves across an edge equals the absolute value of the subtree's "excess" (coins minus nodes), and the total answer is the sum of these absolute values across all edges.
Key Constraints:
1 <= n <= 100- The tree is small, so even a quadratic simulation runs instantly. The difficulty is the algorithmic idea, not raw performance.0 <= Node.val <= n- A node can have zero coins (it needs one) or several (it has a surplus). This imbalance is what creates the redistribution problem.Sum of all Node.val is n- Total coins equals total nodes, so a valid final state always exists and no coins are ever created or destroyed.
Approach 1: Iterative Edge Flow (Parent Map)
Intuition
Every edge in the tree separates a subtree from the rest. Whatever imbalance a subtree has, its surplus or deficit of coins, must cross the single edge connecting it to its parent. So the number of moves on that edge equals the absolute value of the subtree's balance (coins minus nodes), and the answer is the sum over all edges.
We can compute this iteratively without recursion. Collect every node with a BFS that also records each node's parent. Then process the nodes from leaves toward the root. Each node keeps one coin for itself and pushes the rest, its balance of val - 1, up to its parent. That push crosses one edge, so we add abs(balance) to the total and add the balance to the parent's count. When a node has a deficit, the balance is negative and the parent effectively sends coins down, which still counts as abs(balance) moves.
Algorithm
- Build a parent map and a node list with a single BFS from the root.
- Walk the node list in reverse BFS order, so every child is handled before its parent.
- For each node, compute
balance = val - 1and addabs(balance)to the move count. - Add that balance to the node's parent, transferring the surplus or deficit up one edge.
- The root has no parent; its balance settles to zero once every child has pushed up.
- Return the accumulated move count.
Example Walkthrough
Input:
The root has 3 coins; both children have 0. BFS visits the root, then the left and right children, so the reverse order is left child, right child, root.
- Left child: balance = 0 - 1 = -1. Add abs(-1) = 1 move. Push -1 to the root, so root becomes 3 + (-1) = 2.
- Right child: balance = 0 - 1 = -1. Add abs(-1) = 1 move. Push -1 to the root, so root becomes 2 + (-1) = 1.
- Root: balance = 1 - 1 = 0. Add 0 moves. It has no parent, so nothing is pushed.
Total: 2 moves.
Code
- Time Complexity: O(n). The BFS visits each node once to build the parent map and node list, and the reverse pass touches each node once more. Both passes are linear.
- Space Complexity: O(n). The parent map and node list each hold one entry per node, and the BFS queue holds up to O(n) nodes.
This approach already runs in linear time, but it relies on an explicit parent map and an extra node list. The next approach reaches the same answer with a single recursive traversal that carries each subtree's balance back up the call stack, removing the need to store parents at all.
Approach 2: Post-Order DFS (Subtree Excess)
Intuition
Instead of tracking individual coins, count the flow across each edge. Every edge sits between a subtree and the rest of the tree. If a subtree holds more coins than nodes, the surplus must leave through the edge to its parent. If it holds fewer, the shortfall must enter through that same edge.
For a subtree rooted at a node, define its excess as (total coins in subtree) - (number of nodes in subtree). A positive excess means coins move upward through the edge; a negative excess means coins move downward. Either way, the moves across that edge equal |excess|, and the total answer is the sum of |excess| over 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.
A subtree connects to the rest of the tree through exactly one edge: the one joining its root to its parent. So every coin entering or leaving that subtree must cross that single edge, and the count of crossings is fixed by the subtree's balance alone. If the subtree has a surplus, |excess| coins must leave; if it has a shortfall, |excess| coins must enter. No redistribution can do better, because those coins have no other way across.
Summing |childExcess| over every node counts each edge once (each edge is the connection from a child subtree to its parent), so the total equals the minimum number of moves. The excess returned by the root is always 0, since total coins equal total nodes, which confirms the accounting balances.
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).