# 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:

| Constraint | Value |
|---|---:|
| Number of nodes | `1 <= n <= 100` |
| Node value | `0 <= Node.val <= n` |
| Total coins | Sum of all `Node.val` is `n` |

Source: LeetCode 979 problem statement.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Root of a binary tree |
| Output | Minimum number of coin moves |
| Move | Move one coin across one parent-child edge |
| Final state | Every node has exactly one coin |

Function shape:

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

## Examples

Example 1:

```python
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:

```python
2
```

Example 2:

```python
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:

```python
left child -> root
left child -> root
root -> right child
```

That takes `3` moves.

Answer:

```python
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:

```python
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:

```python
balance = coins - nodes
```

| Balance | Meaning |
|---|---|
| Positive | Subtree has extra coins to send upward |
| Negative | Subtree needs coins from its parent |
| Zero | Subtree is already balanced internally |

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

```python
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:

```python
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:

```python
abs(left_balance) + abs(right_balance)
```

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

```python
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

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | Each node is visited once |
| Space | `O(h)` | DFS recursion uses stack space proportional to tree height |

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

## Implementation

```python
# 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:

```python
moves = 0
```

The helper function returns the balance of a subtree:

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

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

```python
if node is None:
    return 0
```

We process children first:

```python
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:

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

Then we return the current subtree's balance:

```python
return left_balance + right_balance + node.val - 1
```

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

## Testing

```python
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()
```

| Test | Expected | Why |
|---|---:|---|
| `[3, 0, 0]` | `2` | Root sends one coin to each child |
| `[0, 3, 0]` | `3` | Left child sends two coins upward, then one goes right |
| `[1]` | `0` | Already balanced |
| `[2, 0, 1]` | `1` | Root sends one coin to left child |
| `[0, 0, 3]` | `3` | Right child sends two coins upward, one moves to left child |