Distribute Coins in Binary Tree

medium binary tree dfs post-order

Problem

You are given the root of a binary tree with n nodes where each node 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 the other (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.

Inputroot = [3, 0, 0]

Output2

From the root with 3 coins, send one coin to each of its two empty children — 2 moves total.

tree (level-order, use 'null' for missing)

def distributeCoins(root):
    moves = 0
    def dfs(node):
        nonlocal moves
        if not node:
            return 0
        left = dfs(node.left)
        right = dfs(node.right)
        moves += abs(left) + abs(right)
        return node.val + left + right - 1
    dfs(root)
    return moves

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

class Solution {
    int moves = 0;
    public int distributeCoins(TreeNode root) {
        dfs(root);
        return moves;
    }
    private int dfs(TreeNode node) {
        if (node == null) return 0;
        int left = dfs(node.left);
        int right = dfs(node.right);
        moves += Math.abs(left) + Math.abs(right);
        return node.val + left + right - 1;
    }
}

class Solution {
public:
    int moves = 0;
    int distributeCoins(TreeNode* root) {
        dfs(root);
        return moves;
    }
    int dfs(TreeNode* node) {
        if (!node) return 0;
        int left = dfs(node->left);
        int right = dfs(node->right);
        moves += abs(left) + abs(right);
        return node->val + left + right - 1;
    }
};

Explanation

Every node needs to end with exactly one coin, and a move shuffles one coin along one edge. The smart way to count moves is to think about each edge separately and ask: how many coins must cross it?

For any subtree, its balance is its total coins minus the number of nodes it contains — that is the surplus (positive) or shortage (negative) it has to settle with the rest of the tree. Whatever that balance is, exactly that many coins flow across the edge to its parent.

A post-order DFS computes this. dfs(node) gets the balances left and right from its children, and the coins crossing those two edges is abs(left) + abs(right), which we add to moves. The absolute value is used because a coin moving up or down still counts as one move.

The node then reports its own balance upward as node.val + left + right - 1 (the - 1 is the coin it keeps for itself).

Example: [3, 0, 0]. The two children each have balance -1 (need one coin), so the root edges carry |-1| + |-1| = 2 coins — the answer is 2 moves.

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