Distribute Coins in Binary Tree

Distribute Coins in Binary Tree

What is this problem about?

The Distribute Coins in Binary Tree coding problem presents a binary tree where each node contains a certain number of coins. The total number of coins in the tree is equal to the total number of nodes. Your goal is to move the coins so that every node has exactly one coin. A "move" consists of moving one coin between two adjacent nodes (parent-child). You need to find the minimum number of moves required to balance the tree.

Why is this asked in interviews?

This "Medium" difficulty problem is a favorite at companies like Google, Meta, and Goldman Sachs. It tests your mastery of Depth-First Search (DFS) and your ability to aggregate information from the bottom up. It evaluations whether you can recognize that the number of moves passing through an edge is determined by the "excess" or "deficit" of coins in the subtree below that edge. It’s a sophisticated test of tree-based logic and greedy optimization.

Algorithmic pattern used

This problem uses Post-order Traversal (DFS).

1. For each node, calculate the "balance" of its subtree. The balance is: node.val + left_balance + right_balance - 1.
2. The number of moves needed to fix the current subtree's balance is abs(left_balance) + abs(right_balance).
3. As you traverse the tree from the leaves up to the root, you accumulate these absolute balances.
4. The balance of a subtree represents the number of coins that must either enter or leave that subtree to make every node inside it have exactly one coin.

Example explanation

Consider a tree: Root(0) -> Left(3), Right(0).

1. Left Child (3): Needs 1 coin, has 3. Balance = $+2$. Moves = $|2| = 2$.
2. Right Child (0): Needs 1 coin, has 0. Balance = $-1$. Moves = $|-1| = 1$.
3. Root (0): Receives $+2$ from left and $-1$ from right. Root's own balance = $0 + 2 - 1 - 1 = 0$. Total moves: $2 + 1 = 3$.

Common mistakes candidates make

• BFS approach: Trying to move coins level by level, which doesn't work because the distance between nodes is structural, not level-based.
• Negative handling: Not using abs() when summing moves. A deficit of 5 coins requires 5 moves to enter, just as an excess of 5 requires 5 moves to leave.
• Incorrect balance formula: Forgetting to subtract 1 (the coin the current node keeps for itself).

Interview preparation tip

Practice "Bottom-Up" tree problems. Many tree problems require you to return a value to the parent that summarizes the state of the entire subtree. In this case, the balance is the "net flow" of coins needed for that subtree.