979 · Distribute Coins in Binary Tree

The return value is a surplus, and it may be negative. The cost is abs(L) + abs(R). This problem teaches that the thing being counted is flow across an edge, not anything about the nodes themselves.

1 — The problem

Every node holds some coins; there are exactly n coins for n nodes. In one move a coin travels along one edge, in either direction. What is the minimum number of moves to leave every node with exactly one?

The difficulty is that this reads like a planning problem — which coin goes where, in what order — and it is not. The reframing:

Every edge is independent. Consider the edge above a subtree. That subtree has some number of coins and some number of nodes; the difference is forced to cross that edge, and the direction is decided by the sign. No planning is required, and no ordering — the answer is a sum over edges.

So define surplus(nd) = coins in this subtree minus nodes in it. Then:

This is the record/return split of LC 543 again, with a different pair of quantities.

2 — Watching coins cross edges

Four moves. Node 3 pushes a surplus of 2 up to its parent; the root's right child reports a deficit of −1 and receives one back. The root itself ends at 0, as it must — the whole tree is balanced by construction.

Notice what is not in the code: no queue of pending coins, no notion of which coin moved where, no ordering. Each edge is charged once, in isolation, and the sum is optimal because every one of those crossings was unavoidable.

2.1 Why abs, and why the sum is a lower bound

• The abs: a surplus of +2 means two coins travel upward; a deficit of −1 means one travels downward. Both cost one move per coin, so the sign carries direction and the magnitude carries cost.
• It is a lower bound: the subtree below an edge must end with exactly as many coins as it has nodes, so the imbalance has no way to resolve except by crossing that edge. You cannot do better than abs(surplus) crossings there.
• It is achievable: those crossings can all be scheduled without conflict, because each edge's traffic is independent of every other edge's. So the bound is tight, and the sum is the answer.

Do not add abs() to the returned value on line 6. The sign is information the parent needs — a subtree short two coins and a subtree with two spare are opposite situations, and collapsing them makes the recursion meaningless.

2.2 The identity that makes it safe

The root always returns 0. There are n coins and n nodes, so the whole tree's surplus is zero by definition — which is a free assertion you can put in the code, and a quick way to check the recurrence is right. If your root returns anything else, the - 1 is missing or misplaced.

3 — Complexity and edge cases

• Time O(n), space O(h). One postorder pass.
• Already balanced (every node holds exactly 1): every surplus is 0 and the answer is 0.
• Single node: it holds 1 coin, surplus 0, zero moves.
• All coins at one leaf: the worst case — the surplus is large near that leaf and shrinks by one per level, so the total is quadratic in the depth. Still O(n) time to compute.
• A node may hold 0 coins and still be a leaf; nothing in the recurrence cares.
• Overflow: not a risk at LeetCode's n ≤ 100, but the accumulated moves is the quantity that would grow, not the surplus.
• Common bug: returning Math.abs(...), destroying the direction.
• Common bug: adding abs(surplus(nd)) at the node instead of abs(L) + abs(R). That charges the edge above the node from inside the node, double-counting every edge except the root's.

4 — Reference implementation

private int moves;

public int distributeCoins(TreeNode root) {
    moves = 0;
    surplus(root);            // always returns 0 — n coins, n nodes
    return moves;
}

private int surplus(TreeNode nd) {
    if (nd == null) return 0;
    int L = surplus(nd.left);
    int R = surplus(nd.right);
    moves += Math.abs(L) + Math.abs(R);   // cost: coins crossing the two edges below
    return nd.val + L + R - 1;          // SIGNED — direction matters
}