Distribute Coins in Binary Tree: Counting the Cost of Balance

LeetCode Distribute Coins in Binary Tree (Problem 979) gives you a binary tree where each node holds some number of coins. The total number of coins equals the total number of nodes. Your job is to redistribute coins so that every node ends up with exactly one coin. A single move transfers one coin between two adjacent nodes (parent to child or child to parent). Return the minimum number of moves required.

The problem

You are given the root of a binary tree with n nodes. Each node has node.val coins, and the total across all nodes is exactly n. In one move, you can transfer a single coin from a node to one of its neighbors (parent or child). Find the minimum number of moves to make every node have exactly one coin.

For example, if the root has 3 coins and both children have 0 coins, you need 2 moves: send one coin from the root to the left child and one coin from the root to the right child.

The brute force approach

You could try to simulate the redistribution directly. At each step, find a node with excess coins, pick a neighboring node that needs one, and move a coin along the shortest path between them. You would count every hop along the way. This works but requires pathfinding between arbitrary nodes, and choosing which coins to move first leads to a combinatorial search. For a tree of any real size, this simulation becomes slow and hard to reason about.

A better idea would be to think about each edge independently. Every coin that needs to travel from one part of the tree to another must cross certain edges. If you could figure out how many coins cross each edge, the total number of crossings is the answer. That is exactly what the optimal approach computes.

The key insight

The formula at each node is simple: excess = node.val + left_excess + right_excess - 1. The -1 accounts for the one coin the current node keeps for itself. Whatever is left over (positive or negative) must flow through the edge to the parent.

Step-by-step walkthrough

Let's trace through a tree where the root has 3 coins and both children have 0.

Notice how the excess values flow naturally. Each child reports its deficit (-1) to the parent. The parent adds up the absolute values of those deficits to count moves, then computes its own excess to pass further up the tree.

The code

def distributeCoins(self, root):
    self.moves = 0

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

    dfs(root)
    return self.moves

Here is what each piece does:

• if not node: return 0 is the base case. A null node has no coins and no needs, so its excess is 0.
• left = dfs(node.left) and right = dfs(node.right) recurse into both subtrees first (post-order). The current node makes its calculation after hearing from both children.
• self.moves += abs(left) + abs(right) counts the coin traffic on the two edges connecting this node to its children. Whether coins flow up or down, each crossing is one move.
• return node.val + left + right - 1 computes the excess for the current node's entire subtree. The node starts with node.val coins, absorbs whatever its children send up (or sends coins down to cover their deficits), and keeps 1 for itself. Whatever remains flows to the parent.

Complexity analysis

Time is O(n). Every node is visited exactly once, and the work at each node is O(1): two additions, two absolute values, and a return.

Space is O(h) where h is the height of the tree. This is the recursion stack depth. For a balanced tree, h = log n. For a completely skewed tree, h = n. No extra data structures are needed.

The building blocks

Post-order traversal with value propagation

The core pattern here is post-order DFS where each node returns a computed value to its parent. You see this in many tree problems: compute something for the children first, combine the results with the current node's data, and return a summary upward.

The skeleton looks like this:

def dfs(node):
    if not node:
        return BASE_CASE
    left = dfs(node.left)
    right = dfs(node.right)
    return COMBINE(node.val, left, right)

This same skeleton powers Diameter of Binary Tree, Binary Tree Maximum Path Sum, and Binary Tree Cameras. The only difference is what you compute and return at each node.

Excess flow on edges

The second building block is the idea of modeling coin movement as flow through edges. Instead of tracking individual coins, you ask: "how many coins must cross this edge?" The absolute value of the subtree excess at a child node tells you exactly that. This reframing turns a potentially complicated simulation into a single pass over the tree.

This pattern shows up whenever you need to count transfers, moves, or shipments in a tree structure. The key is recognizing that every transfer between non-adjacent nodes must pass through every edge on the path, so counting edge crossings is equivalent to counting individual moves.

Edge cases

• Single node: A tree with one node that has 1 coin. No moves needed. The DFS returns immediately with moves = 0.
• All coins on one node: One node holds all n coins, the rest hold 0. The coins must flow outward through every edge, and the total moves equal the sum of distances from that node to all others.
• Two nodes: Root has 2 coins, child has 0. One coin flows down the single edge. Answer: 1.
• Skewed tree (linked list): Coins must travel along the single path. The excess at each node determines how many coins pass through each edge. The algorithm handles this naturally.
• Balanced tree with coins at leaves: Coins may need to flow upward and then back down to other parts of the tree. The excess values capture both directions of flow.
• Every node already has 1 coin: No redistribution needed. Every excess is 0, and the total moves is 0.

From understanding to recall

You just traced through the post-order excess approach and watched it count moves by summing absolute values of child excesses at each node. The logic is clean: process children first, add up the coin traffic on each edge, and return the net excess upward.

But during an interview, will you remember the formula node.val + left + right - 1? Will you remember to take abs(left) + abs(right) for the moves, not the excess itself? Will you remember that null nodes return 0, not -1?

Understanding a solution once is not the same as being able to reproduce it under pressure. Spaced repetition bridges that gap. You practice writing the solution from scratch at increasing intervals, and each time the excess formula and the absolute-value trick become more automatic.

The post-order propagation pattern and the excess flow model are reusable building blocks. Once you can recall them reliably, you can apply them to new tree problems you have never seen before.

Related posts

• Binary Tree Cameras - Another post-order DFS on a binary tree where each node reports a state to its parent. Same bottom-up skeleton with a different decision at each node.
• Diameter of Binary Tree - Post-order DFS that returns depth to the parent while tracking a global maximum. A foundational example of the "return one thing, track another" pattern.
• Binary Tree Maximum Path Sum - Post-order traversal where each node computes the best path through itself. Combines child values with the current node, just like the excess formula here.