Distribute Coins in Binary Tree (LeetCode 979)
Postorder Excess/Deficit Balancing: Sum |excess| Over Every Edge
You are given the root of a binary tree with n nodes where each node in the tree has node.val coins. There are n coins in total throughout the whole tree.
In one move, we may choose two adjacent nodes and move one coin from one node to another. A move may be from parent to child, or from child to parent.
Return the minimum number of moves required to make every node have exactly one coin.
Worked Examples
root = [3,0,0]2
root = [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.
Why It Works & Core Invariant
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
Zero coins are required to make amount 0 (dp[0] = 0). All other amounts are initialized to infinity (float('inf')) to represent unreachable states before computation.
# Base State Anchor
dp = [0] + [float("inf")] * amount| 1 | if node is None: return 0 |
| 2 | left, right = dfs(node.left), dfs(node.right) |
| 3 | moves += abs(left) + abs(right) |
| 4 | return node.val + left + right - 1 |
Target: Distribute Coins in Binary Tree (LeetCode 979). An absent child has no coins and no nodes -- zero excess
Subtree bottom-up aggregation: a node combines child subtree solutions upon backtrack; top-down invariants pass accumulated state down the path.
Base case: if not node: return base; recursive calls on left/right child nodes.
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.
🪄 Breaking Down the Code's "Magic Trick"
def excess(node): if node is None: return 0 left, right = excess(node.left), excess(node.right) moves[0] += abs(left) + abs(right) # every unit of imbalance crosses exactly one edge return node.val + left + right - 1 # this subtree's own leftover surplus/deficit 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.
💡 Summary
Whenever a tree problem asks for a minimum number of single-edge transfers to reach a target state at every node, model each subtree's postorder return value as a signed excess/deficit and sum abs(excess) over every edge — this is the numeric cousin of the tri-state "supply and demand" trick used for Binary Tree Cameras.
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
You will see how a postorder signed excess (coins minus nodes) lets every subtree report its surplus or deficit, with moves summing |excess| over every edge.
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
Forgetting the
- 1term: each node consumes exactly one coin for itself before reporting the remainder upward.Treating a deficit as free: a subtree with too few coins still contributes
abs(excess)moves -- direction of travel doesn't matter, only magnitude.Confusing this with a boolean containment check: unlike Binary Tree Pruning's 'does this subtree contain a 1' decision, this is a numeric balance accumulated with abs(), not a keep/discard decision.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I define a postorder helper
excess(node): a null node returns 0. Otherwise I recurse into both children to getleftandrightexcess. I accumulatemoves += abs(left) + abs(right), since every unit of imbalance in a child subtree must cross the single edge connecting it to this node. I then returnnode.val + left + right - 1as this subtree's own leftover surplus or deficit, after consuming one coin for this node itself. Runs inO(N)time and O(H) stack space.
So: excess(node) = node.val + excess(left) + excess(right) - 1; moves += abs(excess(left)) + abs(excess(right)) at every node.
Complexity & Mathematical Proof
O(N)
Look at the recursive function: `def maxDepth(node):`. For every node in the binary tree, the function executes exactly 2 recursive calls (`maxDepth(node.left)` and `maxDepth(node.right)`) and performs O(1) constant-time arithmetic combining their results (`1 + max(left, right)`). Because each of the N tree nodes is visited and processed exactly once, total time is N · O(1) = O(N).
O(H) Auxiliary
Look at the recursion call stack: Each recursive call adds a new stack frame storing the local `node` pointer. The maximum number of simultaneous stack frames alive at any instant equals the maximum path depth from root to leaf, which is the tree height H. In a balanced binary tree, H = log2(N) -> O(log N) stack memory. In a worst-case skewed tree (linked list), H = N -> O(N) stack memory. We allocate zero heap objects, so auxiliary space is bounded by tree height O(H).
T(N) = 2T(N/2) + O(1) ⟹ O(N)
Look at the recursive function: def maxDepth(node):. For every node in the binary tree, the function executes exactly 2 recursive calls (maxDepth(node.left) and maxDepth(node.right)) and performs O(1) constant-time arithmetic combining their results (1 + max(left, right)). Because each of the N tree nodes is visited and processed exactly once, total time is N · O(1) = O(N).
Derivation Progression
N nodes visited
Every node in the binary tree is entered and exited exactly once.
1 + max(left, right)
Combining child subproblem depths requires a single addition and max comparison in O(1).
T(N) = 2T(N/2) + O(1) ⟹ O(N)
Visiting all N nodes with constant combining work yields strictly O(N) time.
Variable Definitions
Memory Architecture & Bounds
O(H) Recursion stack storing tree height H frames (O(log N) balanced, O(N) skewed)
O(1) Zero heap allocations
O(1) Returns integer tree depth
Boundary Best / Worst Cases
time with stack on balanced tree.
time with stack.
time with stack on skewed tree (linked list shape).
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.
Forgetting the - 1 term (node.val + left + right - 1): each node consumes exactly one coin for itself before reporting the remainder upward. A deficit (negative excess) still contributes abs(excess) moves -- direction doesn't matter, only magnitude.
Core Algorithmic State Invariants
Each recursive invocation evaluates disjoint subtrees independently, synthesizing solutions bottom-up from child return values without cross-branch interference.
Node state is computed from child results (e.g. 1 + max(L, R) for height, or sentinel -1 when balanced condition |L - R| <= 1 fails), bubbling answers toward the root.
Null nodes return mathematical identity values (0 for height/count, True for balance, None for LCA), guaranteeing clean recursion termination in O(H) stack space.
Distribute Coins in Binary Tree (LeetCode 979)
Postorder Excess/Deficit Balancing: Sum |excess| Over Every Edge
You are given the root of a binary tree with n nodes where each node in the tree has node.val coins. There are n coins in total throughout the whole tree.
In one move, we may choose two adjacent nodes and move one coin from one node to another. A move may be from parent to child, or from child to parent.
Return the minimum number of moves required to make every node have 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.
Why It Works & Core Invariant
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
Zero coins are required to make amount 0 (dp[0] = 0). All other amounts are initialized to infinity (float('inf')) to represent unreachable states before computation.
# Base State Anchor
dp = [0] + [float("inf")] * amount| 1 | if node is None: return 0 |
| 2 | left, right = dfs(node.left), dfs(node.right) |
| 3 | moves += abs(left) + abs(right) |
| 4 | return node.val + left + right - 1 |
Target: Distribute Coins in Binary Tree (LeetCode 979). An absent child has no coins and no nodes -- zero excess
Subtree bottom-up aggregation: a node combines child subtree solutions upon backtrack; top-down invariants pass accumulated state down the path.
Base case: if not node: return base; recursive calls on left/right child nodes.
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.
🪄 Breaking Down the Code's "Magic Trick"
def excess(node): if node is None: return 0 left, right = excess(node.left), excess(node.right) moves[0] += abs(left) + abs(right) # every unit of imbalance crosses exactly one edge return node.val + left + right - 1 # this subtree's own leftover surplus/deficit 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.
💡 Summary
Whenever a tree problem asks for a minimum number of single-edge transfers to reach a target state at every node, model each subtree's postorder return value as a signed excess/deficit and sum abs(excess) over every edge — this is the numeric cousin of the tri-state "supply and demand" trick used for Binary Tree Cameras.
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
You will see how a postorder signed excess (coins minus nodes) lets every subtree report its surplus or deficit, with moves summing |excess| over every edge.
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
Forgetting the
- 1term: each node consumes exactly one coin for itself before reporting the remainder upward.Treating a deficit as free: a subtree with too few coins still contributes
abs(excess)moves -- direction of travel doesn't matter, only magnitude.Confusing this with a boolean containment check: unlike Binary Tree Pruning's 'does this subtree contain a 1' decision, this is a numeric balance accumulated with abs(), not a keep/discard decision.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I define a postorder helper
excess(node): a null node returns 0. Otherwise I recurse into both children to getleftandrightexcess. I accumulatemoves += abs(left) + abs(right), since every unit of imbalance in a child subtree must cross the single edge connecting it to this node. I then returnnode.val + left + right - 1as this subtree's own leftover surplus or deficit, after consuming one coin for this node itself. Runs inO(N)time and O(H) stack space.
So: excess(node) = node.val + excess(left) + excess(right) - 1; moves += abs(excess(left)) + abs(excess(right)) at every node.
Complexity & Mathematical Proof
O(N)
Look at the recursive function: `def maxDepth(node):`. For every node in the binary tree, the function executes exactly 2 recursive calls (`maxDepth(node.left)` and `maxDepth(node.right)`) and performs O(1) constant-time arithmetic combining their results (`1 + max(left, right)`). Because each of the N tree nodes is visited and processed exactly once, total time is N · O(1) = O(N).
O(H) Auxiliary
Look at the recursion call stack: Each recursive call adds a new stack frame storing the local `node` pointer. The maximum number of simultaneous stack frames alive at any instant equals the maximum path depth from root to leaf, which is the tree height H. In a balanced binary tree, H = log2(N) -> O(log N) stack memory. In a worst-case skewed tree (linked list), H = N -> O(N) stack memory. We allocate zero heap objects, so auxiliary space is bounded by tree height O(H).
T(N) = 2T(N/2) + O(1) ⟹ O(N)
Look at the recursive function: def maxDepth(node):. For every node in the binary tree, the function executes exactly 2 recursive calls (maxDepth(node.left) and maxDepth(node.right)) and performs O(1) constant-time arithmetic combining their results (1 + max(left, right)). Because each of the N tree nodes is visited and processed exactly once, total time is N · O(1) = O(N).
Derivation Progression
N nodes visited
Every node in the binary tree is entered and exited exactly once.
1 + max(left, right)
Combining child subproblem depths requires a single addition and max comparison in O(1).
T(N) = 2T(N/2) + O(1) ⟹ O(N)
Visiting all N nodes with constant combining work yields strictly O(N) time.
Variable Definitions
Memory Architecture & Bounds
O(H) Recursion stack storing tree height H frames (O(log N) balanced, O(N) skewed)
O(1) Zero heap allocations
O(1) Returns integer tree depth
Boundary Best / Worst Cases
time with stack on balanced tree.
time with stack.
time with stack on skewed tree (linked list shape).
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.
Forgetting the - 1 term (node.val + left + right - 1): each node consumes exactly one coin for itself before reporting the remainder upward. A deficit (negative excess) still contributes abs(excess) moves -- direction doesn't matter, only magnitude.
Core Algorithmic State Invariants
Each recursive invocation evaluates disjoint subtrees independently, synthesizing solutions bottom-up from child return values without cross-branch interference.
Node state is computed from child results (e.g. 1 + max(L, R) for height, or sentinel -1 when balanced condition |L - R| <= 1 fails), bubbling answers toward the root.
Null nodes return mathematical identity values (0 for height/count, True for balance, None for LCA), guaranteeing clean recursion termination in O(H) stack space.
| Canonical Invariant | Concrete Code | Engineering Rationale |
|---|---|---|
| if node is None: return 0 | if node is None: return 0 | An absent child has no coins and no nodes -- zero excess |
| left_excess, right_excess = dfs_excess(node.left, ...), dfs_excess(node.right, ...) | left, right = excess(node.left), excess(node.right) | Postorder: both children must settle their own surplus/deficit before reporting upward |
| moves[0] += abs(left_excess) + abs(right_excess); return node.val + left_excess + right_excess - 1 | moves += abs(left) + abs(right); return node.val + left + right - 1 | Every unit of imbalance crosses exactly one edge; the -1 accounts for this node keeping one coin for itself |