Distribute Coins in Binary Tree — LC 979 Post-Order Flow Analysis

Problem Statement#

LeetCode 979 — Distribute Coins in Binary Tree | Difficulty: Medium

You are given the root of a binary tree with n nodes. Each node has node.val coins. There are n coins in total. In one move, you may choose two adjacent nodes and move one coin from one node to the other. Return the minimum number of moves required to make every node have exactly one coin.

Constraints:

• The number of nodes is n where 1 <= n <= 100
• 0 <= Node.val <= n
• The sum of all Node.val is n

Input:  root = [3,0,0]
Output: 2
Explanation: Move one coin from root to left child, one coin to right child.

Input:  root = [0,3,0]
Output: 3
Explanation: Move two coins from node 3 to its sibling (via parent), one more to the root.

Why This Problem Matters#

Distribute Coins is a FAANG interview favorite because it reframes a seemingly complex distribution problem as a simple edge-flow problem. Amazon and Google use it to test whether candidates can find elegant O(n) solutions by changing the mental model — instead of thinking about which coins move where, think about how many coins cross each edge.

The insight generalizes to many "flow on trees" problems: LC 968 (Binary Tree Cameras), LC 337 (House Robber III), LC 543 (Diameter of Binary Tree). The post-order DFS pattern that returns a "net value flowing upward through this edge" is a reusable template.

The Core Insight#

The number of moves equals the total number of coin crossings across all edges. For each edge, the number of coins crossing it equals the absolute value of the "excess" in the subtree below that edge.

Excess of a subtree = (total coins in subtree) - (number of nodes in subtree) = net surplus (+) or deficit (-).

If a subtree has excess = +3, then 3 coins must cross the edge upward (into the parent). If excess = -2, then 2 coins must cross the edge downward (into the subtree). Either way, |excess| moves happen on that edge.

Post-order DFS: dfs(node) returns the excess for the subtree rooted at node.

• Excess at leaf: node.val - 1 (one coin stays, the rest flow out)
• Excess at internal node: node.val + excess_left + excess_right - 1
• Moves accumulated: |excess_left| + |excess_right| for each internal node

Visual Dry Run#

Tree: [0, 3, 0]

Total moves = 3. Answer = 3.

Verification: node 3 sends 2 coins upward (2 moves), root receives 1, sends 1 downward to right child (1 move). But root also needs 1 coin, so node 3 sends 1 to root (1 move) and 2 to right (2 moves via root). Total = 3. Correct.

Solution (Optimal)#

class Solution:
    def distributeCoins(self, root) -> int:
        self.moves = 0
 
        def dfs(node):
            if not node:
                return 0
 
            left_excess = dfs(node.left)
            right_excess = dfs(node.right)
 
            # Each coin crossing an edge = one move
            self.moves += abs(left_excess) + abs(right_excess)
 
            # Return net excess for this subtree
            # (coins available) - (coins needed = 1 per node)
            return node.val + left_excess + right_excess - 1
 
        dfs(root)
        return self.moves

var distributeCoins = function(root) {
    let moves = 0;
 
    function dfs(node) {
        if (!node) return 0;
 
        const leftExcess = dfs(node.left);
        const rightExcess = dfs(node.right);
 
        // Accumulate moves: one per coin crossing this edge
        moves += Math.abs(leftExcess) + Math.abs(rightExcess);
 
        // Net excess flowing up through edge to parent
        return node.val + leftExcess + rightExcess - 1;
    }
 
    dfs(root);
    return moves;
};

Time: O(n) — each node visited exactly once in post-order Space: O(h) — recursion call stack; O(log n) balanced, O(n) skewed

Common Mistakes#

• Trying to simulate actual coin movements instead of computing excess flow
• Forgetting the -1 in the return value (node.val + left + right - 1) — each node "consumes" one coin
• Adding excess_left + excess_right to moves instead of |excess_left| + |excess_right| — direction does not matter, only the amount crossing the edge
• Not handling the null base case (returning 0 for null nodes)

Interview Tips#

• Reframe the problem early: "Instead of tracking which coins move, count how many coins cross each edge"
• The return value node.val + left + right - 1 means "net coins flowing out of this subtree to the parent"
• Positive return = surplus flowing up; negative return = deficit needing coins from parent
• Both positive and negative excess count as moves on the edge — hence the absolute value

Follow-up Questions#

• What if nodes need k coins each (not 1)? Change -1 to -k in the excess formula. The same DFS structure works.
• What if coins can only move upward (from child to parent)? The problem becomes much harder — you cannot balance a subtree deficit from above.
• How would you reconstruct which coins moved where? You would need to track actual coin paths, which requires storing the excess as you go and backtracking.
• What if some nodes are blocked (cannot transfer coins)? Use a DFS that treats blocked edges as isolated subtrees, solving each independently.

Key Takeaways#

• Distribute Coins converts a movement problem into an edge-flow problem: moves = sum of |excess| over all edges
• Post-order DFS computes subtree excess: node.val + left_excess + right_excess - 1
• Positive excess means surplus coins flow upward; negative means deficit requiring coins from parent
• Absolute value is used because both directions count as moves
• Time O(n), space O(h) — optimal since you must visit every node
• The excess/flow pattern on trees applies to any problem asking "how much passes through each edge"
• The -1 in the return value is the key: each node "keeps" exactly one coin and flows the rest