Distribute Coins in Binary Tree

Problem

A binary tree has n nodes, n coins total. In one move, a coin moves along an edge. Return minimum moves to give each node exactly one coin.

Key insight: Each edge carries |excess| coins. Excess of subtree = sum of coins - number of nodes. Post-order: propagate excess upward, add abs(excess) to move count.

Solutions

// C
int moves = 0;
int dfs(TreeNode* node) {
    if (!node) return 0;
    int l = dfs(node->left), r = dfs(node->right);
    moves += abs(l) + abs(r);
    return node->val + l + r - 1; // excess coins
}
int distributeCoins(TreeNode* root) {
    moves = 0;
    dfs(root);
    return moves;
}

// C++
int moves = 0;
int dfs(TreeNode* node) {
    if (!node) return 0;
    int l = dfs(node->left), r = dfs(node->right);
    moves += abs(l) + abs(r);
    return node->val + l + r - 1;
}
int distributeCoins(TreeNode* root) {
    moves = 0; dfs(root); return moves;
}

// Java
int moves = 0;
public int distributeCoins(TreeNode root) {
    dfs(root); return moves;
}
int dfs(TreeNode node) {
    if (node == null) return 0;
    int l = dfs(node.left), r = dfs(node.right);
    moves += Math.abs(l) + Math.abs(r);
    return node.val + l + r - 1;
}

// JavaScript
function distributeCoins(root) {
    let moves = 0;
    function dfs(node) {
        if (!node) return 0;
        const l = dfs(node.left), r = dfs(node.right);
        moves += Math.abs(l) + Math.abs(r);
        return node.val + l + r - 1;
    }
    dfs(root);
    return moves;
}

# Python
def distributeCoins(root):
    moves = [0]
    def dfs(node):
        if not node:
            return 0
        l, r = dfs(node.left), dfs(node.right)
        moves[0] += abs(l) + abs(r)
        return node.val + l + r - 1  # excess = coins - 1 needed
    dfs(root)
    return moves[0]

Complexity

Time: O(n)
Space: O(h)

Key Insight

dfs(node) returns the net flow through the edge above node (positive = excess sent up, negative = deficit needing coins from up). Each edge flow = one move per coin.