Distribute Coins in Binary Tree

MediumTrees · DFS (Post-order Balance)🧩 Tree DFS LeetCode #979 ↗Updated Oct 30, 2026

Problem

A binary tree has n nodes and node i holds node.val coins; the tree holds exactly n coins in total. One move carries a single coin across one edge (parent ↔ child). Return the minimum number of moves after which every node holds exactly one coin.

Inputroot = [1,0,2]Output2

Inputroot = [0,0,0,4]Output6

Inputroot = [1]Output0

1 ≤ n ≤ 100 · 0 ≤ Node.val ≤ n · sum of all Node.val = n

Try it yourself

Java

class Solution {
    public int distributeCoins(TreeNode root) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Look at one edge at a time. If the subtree below an edge has c coins and s nodes, exactly |c − s| coins must cross that edge (out if surplus, in if deficit) — and that many crossings is enough. The answer is the sum of |excess| over all edges, which one post-order pass computes.

PatternTree DFS

Instinct If the answer for a node can be built from the answers of its left and right subtrees, write one recursive function and trust it on the children.

Memory hack Ask the kids, then decide - each child reports up, the parent combines, and a global variable keeps the best "bend" seen so far.

Open the Tree DFS guide →

Approaches

Brute ForceRecount Every Subtree per Edge

Time O(n · h)Space O(h)

Visit every non-root node; for the edge above it, count the coins and the nodes in its subtree with two fresh traversals and add |coins − size|. Correct by the edge argument, but each node is re-counted once for every ancestor.

Java

public int distributeCoins(TreeNode root) {
    int moves = 0;
    Deque<TreeNode> stack = new ArrayDeque<>();
    if (root != null) stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        for (TreeNode child : new TreeNode[]{node.left, node.right}) {
            if (child == null) continue;
            // coins that must cross the edge node -> child
            moves += Math.abs(coins(child) - size(child));
            stack.push(child);
        }
    }
    return moves;
}
private int coins(TreeNode node) {
    return node == null ? 0 : node.val + coins(node.left) + coins(node.right);
}
private int size(TreeNode node) {
    return node == null ? 0 : 1 + size(node.left) + size(node.right);
}

Proves the formula, but a skewed tree (h = n) makes it O(n²).

BetterMemoized Excess Map (Two Passes)

Time O(n)Space O(n)

First, one post-order pass stores excess(node) = coins − size of every subtree in a HashMap, built from the children's stored values. Second, sum |excess| over every node except the root (whose excess is always 0).

Java

public int distributeCoins(TreeNode root) {
    Map<TreeNode, Integer> excess = new HashMap<>();
    fill(root, excess);
    int moves = 0;
    for (Map.Entry<TreeNode, Integer> e : excess.entrySet())
        if (e.getKey() != root) moves += Math.abs(e.getValue());
    return moves;
}
private int fill(TreeNode node, Map<TreeNode, Integer> excess) {
    if (node == null) return 0;
    int value = node.val - 1 + fill(node.left, excess) + fill(node.right, excess);
    excess.put(node, value);
    return value;
}

Linear time, but keeps an O(n) map that the answer never really needs.

OptimalSingle Post-order Pass Returning Excess

Time O(n)Space O(h)

dfs(node) returns how many coins its subtree must send up (negative = must receive). Before returning, the node adds |left| + |right| to the move counter, because exactly those coins travel across its two child edges. Nothing is stored beyond the recursion stack.

Java

private int moves;

public int distributeCoins(TreeNode root) {
    moves = 0;
    dfs(root);
    return moves;
}
// Returns coins this subtree has in surplus (negative = deficit).
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 - 1 + left + right;
}

One traversal, O(h) memory — the expected interview answer.

Pro tip

Say it in one line: “each edge carries |excess of the subtree below it| coins”. The code then writes itself.

At a glance

Level	Approach	Time	Space
Brute Force	Recount Every Subtree per Edge	`O(n · h)`	`O(h)`
Better	Memoized Excess Map (Two Passes)	`O(n)`	`O(n)`
Optimal	Single Post-order Pass Returning Excess	`O(n)`	`O(h)`

Common pitfalls

Adding signed excess instead of Math.abs — coins flowing in also cost moves.
Returning node.val + left + right without the − 1 the node keeps for itself.
Trying to simulate coin hops greedily — it is slow and easy to get wrong; count per edge instead.

Interview tips

Draw one edge and argue the lower bound |coins − nodes| and that it is achievable.
Explain that negative excess means coins flow downward through that edge.
Mention the root's excess is always 0 because the total equals n.

Pattern

Post-order DFS returning a subtree aggregate → when each edge's cost depends only on a summary (sum, count, balance) of the subtree below it.

My notes saved in this browser