Distribute Coins in Binary Tree (LeetCode 979)
You're given the root of an n-node binary tree where each node is holding node.val coins, and the coins across the whole tree add up to exactly n.
A move slides a single coin between two nodes that are directly connected — parent to child, or child to parent.
Work out the minimum number of moves needed so every node ends up holding exactly one coin.
Worked Examples
root = [3,0,0]2root = [0,3,0]3⚖️Formal Constraints & Bounds
The number of nodes in the tree is n.1 <= n <= 1000 <= Node.val <= nThe sum of all Node.val is n.
Core Insight
Every subtree's excess (coins minus nodes) must cross the single edge to its parent -- the direction doesn't matter, only the magnitude. Postorder DFS accumulates abs(left_excess) + abs(right_excess) at every node and returns node.val + left + right - 1 (the -1 accounts for this node keeping one coin for itself).
Real-World Scenario & Production Applications
Load-balancing resource redistribution across a hierarchical server topology, minimum-transfer inventory rebalancing across a warehouse tree network.
Subproblems & Recurrence Decomposition3 Phases
A null child holds no coins and needs none, so it reports an excess of 0.
if node is None:
return 0| 1 | if not node: |
| 2 | return 0 |
| 3 | left = excess(node.left) |
| 4 | right = excess(node.right) |
| 5 | moves += abs(left) + abs(right) |
| 6 | return node.val + left + right - 1 |
Conceptual Narrative
🧠 Pattern Intuition & Real-World Analogy
This is the "Supply and Demand" sibling of Binary Tree Cameras: instead of a discrete tri-state code, each subtree reports a signed quantity — how much surplus or shortage of coins it is carrying — and every edge pays for the imbalance that crosses it.
🏦 The Analogy: A Chain of Branch Banks Settling Cash Imbalances
Imagine a hierarchy of bank branches, each starting the day with some amount of cash and each needing to end the day with exactly one unit in its own till. Each branch first settles its own child branches: any branch with too much cash sends its surplus down to headquarters via the one road connecting them (or asks for more if it's short), and every unit that travels along that specific road counts as one "move," regardless of which direction it travels. Once a branch has settled up with all of its children, whatever surplus or shortage remains rolls up to be handled with its own parent branch, one level higher.
🔑 The Key Idea in the Code
abs(left) + abs(right) is the entire trick: it doesn't matter whether a child subtree has too many coins (positive excess, coins flow down-to-up) or too few (negative excess, coins flow up-to-down) — either way, exactly abs(excess) coins must cross that one edge, so the move count only cares about magnitude, never sign.
Forgetting the
- 1term: Returningnode.val + left + rightinstead ofnode.val + left + right - 1. Each node keeps exactly one coin for itself before reporting its surplus or deficit upward; omitting the-1silently double-counts every node's own coin.Treating a deficit as free: Only accumulating
moveswhenleft/rightis positive (surplus flowing up) and skipping negative excess (a deficit flowing down). The direction a coin travels across an edge doesn't matter for counting moves --abs(left) + abs(right)must be accumulated regardless of sign.Accumulating moves at the wrong node: Adding
abs(left) + abs(right)from inside the child's own call instead of at the parent, after both children have returned. Each edge's cost is charged exactly once, at the parent that receives the child's excess.Forgetting the global counter is order-independent: Assuming coins must physically move in a particular sequence to achieve the minimum count. The postorder sum of
abs(excess)over every edge is provably optimal regardless of the order moves are actually performed in.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Exactly one coin per node, minimum number of moves sliding a coin along an edge between adjacent nodes.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: a subtree with signed excess k (surplus if positive, deficit if negative) must move exactly |k| coins across the single edge to its parent.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
The card's trap: return the signed surplus and take
absonly when adding tomoves.The root's own
excessis always 0 (the tree has as many coins as nodes), so returningexcess(root)instead ofmovesreturns 0.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use Greedy Tree DP. Coins can only enter or leave a subtree through the one edge to its parent, so for every subtree I compute its surplus: the coins it holds minus the number of nodes, which is the node's coins plus both children's surpluses minus one for the node itself. Whatever that number is, that many coins must cross the edge above the subtree, in one direction or the other, and settling each subtree with its parent in postorder never moves more than that. So at each node I add the absolute values of the two children's surpluses to the move count, and return my own signed surplus. The trap is where the absolute value goes: if I returned it, a subtree that is short two coins would look like it had two to spare. The answer is the move count, not the root's surplus, which is always zero. It's
O(N)time and O(H) recursion stack.
Complexity & Mathematical Proof
O(N)
Look at excess(node): each node is visited once and does O(1) arithmetic — two absolute values, one addition to moves, and one return value. No coin move is ever simulated; moves are counted from excess magnitudes.
O(H) Auxiliary
The recursion stack holds one frame per level of the current path, so auxiliary space is the tree height H. moves is a single integer.
T(N) = N · O(1) = O(N)
Derivation Progression
N node visits
Every node is entered once, after both children return their excess.
O(1) Work Per Framemoves += |left| + |right|
Each edge's cost is its child's excess magnitude, added once.
O(N)
N frames with constant work each.
Variable Definitions
Total number of nodes (and coins) in the tree
Tree height (log N in a balanced tree, N in a skewed tree)
Memory Architecture & Bounds
O(H) recursion frames
O(1) move counter
O(1) returns one integer
Boundary Best / Worst Cases
time with stack on a balanced tree.
time.
time with stack on a skewed tree.
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "exactly one coin per node", "minimum number of moves", "slide a coin along an edge". Postorder Excess/Deficit Balancing: every subtree reports a signed "excess" (coins minus nodes) to its parent; total work is over every edge.
. Time budget is strictly , one postorder pass.
At LeetCode's recursion is safe, but a deep hierarchy of thousands of levels passes CPython's default recursion limit of 1000: run the same postorder with an explicit stack.
Distribute Coins in Binary Tree (LeetCode 979)
You're given the root of an n-node binary tree where each node is holding node.val coins, and the coins across the whole tree add up to exactly n.
A move slides a single coin between two nodes that are directly connected — parent to child, or child to parent.
Work out the minimum number of moves needed so every node ends up holding exactly one coin.
Worked Examples
root = [3,0,0]2root = [0,3,0]3⚖️Formal Constraints & Bounds
The number of nodes in the tree is n.1 <= n <= 1000 <= Node.val <= nThe sum of all Node.val is n.
Core Insight
Every subtree's excess (coins minus nodes) must cross the single edge to its parent -- the direction doesn't matter, only the magnitude. Postorder DFS accumulates abs(left_excess) + abs(right_excess) at every node and returns node.val + left + right - 1 (the -1 accounts for this node keeping one coin for itself).
Real-World Scenario & Production Applications
Load-balancing resource redistribution across a hierarchical server topology, minimum-transfer inventory rebalancing across a warehouse tree network.
Subproblems & Recurrence Decomposition3 Phases
A null child holds no coins and needs none, so it reports an excess of 0.
if node is None:
return 0| 1 | if not node: |
| 2 | return 0 |
| 3 | left = excess(node.left) |
| 4 | right = excess(node.right) |
| 5 | moves += abs(left) + abs(right) |
| 6 | return node.val + left + right - 1 |
Conceptual Narrative
🧠 Pattern Intuition & Real-World Analogy
This is the "Supply and Demand" sibling of Binary Tree Cameras: instead of a discrete tri-state code, each subtree reports a signed quantity — how much surplus or shortage of coins it is carrying — and every edge pays for the imbalance that crosses it.
🏦 The Analogy: A Chain of Branch Banks Settling Cash Imbalances
Imagine a hierarchy of bank branches, each starting the day with some amount of cash and each needing to end the day with exactly one unit in its own till. Each branch first settles its own child branches: any branch with too much cash sends its surplus down to headquarters via the one road connecting them (or asks for more if it's short), and every unit that travels along that specific road counts as one "move," regardless of which direction it travels. Once a branch has settled up with all of its children, whatever surplus or shortage remains rolls up to be handled with its own parent branch, one level higher.
🔑 The Key Idea in the Code
abs(left) + abs(right) is the entire trick: it doesn't matter whether a child subtree has too many coins (positive excess, coins flow down-to-up) or too few (negative excess, coins flow up-to-down) — either way, exactly abs(excess) coins must cross that one edge, so the move count only cares about magnitude, never sign.
Forgetting the
- 1term: Returningnode.val + left + rightinstead ofnode.val + left + right - 1. Each node keeps exactly one coin for itself before reporting its surplus or deficit upward; omitting the-1silently double-counts every node's own coin.Treating a deficit as free: Only accumulating
moveswhenleft/rightis positive (surplus flowing up) and skipping negative excess (a deficit flowing down). The direction a coin travels across an edge doesn't matter for counting moves --abs(left) + abs(right)must be accumulated regardless of sign.Accumulating moves at the wrong node: Adding
abs(left) + abs(right)from inside the child's own call instead of at the parent, after both children have returned. Each edge's cost is charged exactly once, at the parent that receives the child's excess.Forgetting the global counter is order-independent: Assuming coins must physically move in a particular sequence to achieve the minimum count. The postorder sum of
abs(excess)over every edge is provably optimal regardless of the order moves are actually performed in.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Exactly one coin per node, minimum number of moves sliding a coin along an edge between adjacent nodes.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: a subtree with signed excess k (surplus if positive, deficit if negative) must move exactly |k| coins across the single edge to its parent.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
The card's trap: return the signed surplus and take
absonly when adding tomoves.The root's own
excessis always 0 (the tree has as many coins as nodes), so returningexcess(root)instead ofmovesreturns 0.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use Greedy Tree DP. Coins can only enter or leave a subtree through the one edge to its parent, so for every subtree I compute its surplus: the coins it holds minus the number of nodes, which is the node's coins plus both children's surpluses minus one for the node itself. Whatever that number is, that many coins must cross the edge above the subtree, in one direction or the other, and settling each subtree with its parent in postorder never moves more than that. So at each node I add the absolute values of the two children's surpluses to the move count, and return my own signed surplus. The trap is where the absolute value goes: if I returned it, a subtree that is short two coins would look like it had two to spare. The answer is the move count, not the root's surplus, which is always zero. It's
O(N)time and O(H) recursion stack.
Complexity & Mathematical Proof
O(N)
Look at excess(node): each node is visited once and does O(1) arithmetic — two absolute values, one addition to moves, and one return value. No coin move is ever simulated; moves are counted from excess magnitudes.
O(H) Auxiliary
The recursion stack holds one frame per level of the current path, so auxiliary space is the tree height H. moves is a single integer.
T(N) = N · O(1) = O(N)
Derivation Progression
N node visits
Every node is entered once, after both children return their excess.
O(1) Work Per Framemoves += |left| + |right|
Each edge's cost is its child's excess magnitude, added once.
O(N)
N frames with constant work each.
Variable Definitions
Total number of nodes (and coins) in the tree
Tree height (log N in a balanced tree, N in a skewed tree)
Memory Architecture & Bounds
O(H) recursion frames
O(1) move counter
O(1) returns one integer
Boundary Best / Worst Cases
time with stack on a balanced tree.
time.
time with stack on a skewed tree.
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "exactly one coin per node", "minimum number of moves", "slide a coin along an edge". Postorder Excess/Deficit Balancing: every subtree reports a signed "excess" (coins minus nodes) to its parent; total work is over every edge.
. Time budget is strictly , one postorder pass.
At LeetCode's recursion is safe, but a deep hierarchy of thousands of levels passes CPython's default recursion limit of 1000: run the same postorder with an explicit stack.