LeetCode 979: Distribute Coins in Binary Tree

Problem Restatement

We are given the root of a binary tree with n nodes.

Each node has some number of coins stored in node.val.

There are exactly n coins total in the whole tree, so it is possible for every node to end with exactly one coin.

In one move, we may move one coin between two adjacent nodes. Adjacent means parent and child.

We need to return the minimum number of moves needed so that every node has exactly one coin.

The official constraints are:

Source: LeetCode 979 problem statement.

Input and Output

Function shape:

def distributeCoins(root: Optional[TreeNode]) -> int:
    ...

Examples

Example 1:

root = [3, 0, 0]

The root has 3 coins.

Both children have 0 coins.

We move one coin from the root to the left child, and one coin from the root to the right child.

Answer:

2

Example 2:

root = [0, 3, 0]

The left child has 3 coins.

The root has 0 coins.

The right child has 0 coins.

One possible optimal sequence:

left child -> root
left child -> root
root -> right child

That takes 3 moves.

Answer:

3

First Thought: Simulate Coin Movement

A direct way is to think about moving coins one by one.

If a node has too many coins, send extras to nearby nodes that need coins.

If a node has too few coins, pull coins from nearby nodes that have extras.

But this becomes hard to implement cleanly. A coin may need to move through several edges, and deciding the exact movement order is unnecessary.

We only need the number of moves.

Key Insight

Look at one subtree.

Suppose a subtree has:

coins = total number of coins inside the subtree
nodes = total number of nodes inside the subtree

If coins > nodes, the subtree has extra coins. Those extra coins must leave the subtree through the edge connecting it to its parent.

If coins < nodes, the subtree needs coins. Those missing coins must enter the subtree through the edge connecting it to its parent.

So the important value is:

balance = coins - nodes

The number of moves across the edge from this subtree to its parent is:

abs(balance)

This is why a postorder DFS works well. We first solve the children, then return each subtree’s balance to its parent.

Algorithm

Use DFS.

For each node, compute the balance of its subtree.

The balance is:

left_balance + right_balance + node.val - 1

Why subtract 1?

Because the current node needs to keep exactly one coin for itself.

During DFS:

1. Recursively compute the left subtree balance.
2. Recursively compute the right subtree balance.
3. Add abs(left_balance) + abs(right_balance) to the answer.
4. Return left_balance + right_balance + node.val - 1.

The answer counts how many coins cross each edge.

Correctness

For any subtree, the only way coins can enter or leave that subtree is through the edge between the subtree root and its parent.

If the subtree has balance k > 0, then it has k extra coins. Those k coins must cross that parent edge upward.

If the subtree has balance k < 0, then it lacks -k coins. Those -k coins must cross that parent edge downward.

Therefore, the number of required moves across that edge is abs(k).

The DFS computes this balance for each child subtree. At a node, the moves needed between the node and its children are exactly:

abs(left_balance) + abs(right_balance)

After those moves are counted, the current subtree’s remaining balance is:

left_balance + right_balance + node.val - 1

This value is returned to the parent.

Every move crosses exactly one edge. The algorithm counts the required flow across every edge exactly once, when processing the parent of that edge. Since every valid final distribution must move exactly that many coins across each edge, and the algorithm sums those necessary moves, the result is minimal.

Complexity

Here, n is the number of nodes and h is the height of the tree.

Implementation

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def distributeCoins(self, root: Optional[TreeNode]) -> int:
        moves = 0

        def dfs(node: Optional[TreeNode]) -> int:
            nonlocal moves

            if node is None:
                return 0

            left_balance = dfs(node.left)
            right_balance = dfs(node.right)

            moves += abs(left_balance) + abs(right_balance)

            return left_balance + right_balance + node.val - 1

        dfs(root)
        return moves

Code Explanation

We store the answer in:

moves = 0

The helper function returns the balance of a subtree:

def dfs(node: Optional[TreeNode]) -> int:

An empty subtree has no coins and no nodes, so its balance is 0:

if node is None:
    return 0

We process children first:

left_balance = dfs(node.left)
right_balance = dfs(node.right)

This is postorder traversal.

The left subtree must send or receive abs(left_balance) coins through the left edge.

The right subtree must send or receive abs(right_balance) coins through the right edge.

So we add:

moves += abs(left_balance) + abs(right_balance)

Then we return the current subtree’s balance:

return left_balance + right_balance + node.val - 1

The -1 means the current node keeps one coin for itself.

Testing

from typing import Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def run_tests():
    s = Solution()

    root1 = TreeNode(3, TreeNode(0), TreeNode(0))
    assert s.distributeCoins(root1) == 2

    root2 = TreeNode(0, TreeNode(3), TreeNode(0))
    assert s.distributeCoins(root2) == 3

    root3 = TreeNode(1)
    assert s.distributeCoins(root3) == 0

    root4 = TreeNode(2, TreeNode(0), TreeNode(1))
    assert s.distributeCoins(root4) == 1

    root5 = TreeNode(0, TreeNode(0), TreeNode(3))
    assert s.distributeCoins(root5) == 3

    print("all tests passed")

run_tests()