# Distribute Coins in Binary Tree
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/distribute-coins-in-binary-tree)
Canonical: https://scaleengineer.com/dsa/problems/distribute-coins-in-binary-tree
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Tree, Binary Tree
**Companies:** [PhonePe](https://scaleengineer.com/companies/phonepe)
---
## Problem
You are given the `root` of a binary tree with `n` nodes where each `node` in the tree has `node.val` coins. There are `n` coins in total throughout the whole tree.

In one move, we may choose two adjacent nodes and move one coin from one node to another. A move may be from parent to child, or from child to parent.

Return _the **minimum** number of moves required to make every node have **exactly** one coin_.

**Example 1:**

![](https://assets.glich.co/dsa/distribute-coins-in-binary-tree/image0.png) 

**Input:** root = [3,0,0]
**Output:** 2
**Explanation:** From the root of the tree, we move one coin to its left child, and one coin to its right child.

**Example 2:**

![](https://assets.glich.co/dsa/distribute-coins-in-binary-tree/image1.png) 

**Input:** root = [0,3,0]
**Output:** 3
**Explanation:** From the left child of the root, we move two coins to the root [taking two moves]. Then, we move one coin from the root of the tree to the right child.

**Constraints:**

* The number of nodes in the tree is `n`.
* `1 <= n <= 100`
* `0 <= Node.val <= n`
* The sum of all `Node.val` is `n`.

# Approaches
## Two-Pass Depth-First Search
This approach breaks the problem into two distinct phases. First, we traverse the tree to gather information about each subtree: the number of nodes and the total number of coins. This information is stored in a map. In the second phase, we iterate through the stored information. For each subtree, the absolute difference between its total coins and its size represents the number of coins that must move across the edge connecting it to its parent. The sum of these values over all subtrees gives the total minimum moves.
**Time:** O(N), where N is the number of nodes. The first pass (DFS) visits each node once, taking O(N) time. The second pass iterates through the N entries in the map, also taking O(N) time. Thus, the total time complexity is O(N) + O(N) = O(N). · **Space:** O(N), where N is the number of nodes. This is dominated by the HashMap used to store the size and coin sum for each of the N subtrees. The recursion stack for the DFS also contributes O(H) space, where H is the tree height.
**Pros:** Conceptually clear by separating the problem into two steps: data gathering and calculation.; The logic is straightforward to follow.
**Cons:** Requires extra space (O(N)) for the map, which is less efficient than a single-pass approach.; Involves two separate phases (a full traversal and then an iteration over the collected data), making it less concise.
### Explanation
The core idea is that for any subtree, if it has `s` nodes, it must eventually hold `s` coins for the final configuration to be valid. If its current coin total is `c`, then `|c - s|` coins must be moved across the single edge that connects this subtree to its parent. The total number of moves is the sum of moves across all edges.

**Pass 1: Gather Subtree Information**
We use a post-order DFS traversal. A helper function, say `gatherInfo(node)`, recursively calls itself on its children and then combines the results. For each node, it computes the size of its subtree and the sum of coins within it and stores this pair of values in a `HashMap<TreeNode, int[]>`. 

**Pass 2: Calculate Moves**
After the map is populated, we can calculate the total moves. The number of moves across the edge connecting a node `u` to its parent is `|coin_sum_of_u's_subtree - size_of_u's_subtree|`. By summing this quantity for all nodes in the tree, we get the total number of moves. The root's subtree balance is always zero (`n` coins, `n` nodes), so it contributes 0 to the sum.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    // Map to store {node -> [subtree_size, subtree_coin_sum]}
    private Map<TreeNode, int[]> subtreeInfo;

    public int distributeCoins(TreeNode root) {
        subtreeInfo = new HashMap<>();
        
        // Pass 1: Gather information
        gatherInfo(root);
        
        // Pass 2: Calculate moves
        int totalMoves = 0;
        for (int[] info : subtreeInfo.values()) {
            // info[0] is size, info[1] is coin sum
            totalMoves += Math.abs(info[1] - info[0]);
        }
        
        return totalMoves;
    }

    private int[] gatherInfo(TreeNode node) {
        if (node == null) {
            return new int[]{0, 0};
        }
        
        int[] leftInfo = gatherInfo(node.left);
        int[] rightInfo = gatherInfo(node.right);
        
        int size = 1 + leftInfo[0] + rightInfo[0];
        int coins = node.val + leftInfo[1] + rightInfo[1];
        
        subtreeInfo.put(node, new int[]{size, coins});
        return new int[]{size, coins};
    }
}
```
### Algorithm
- Create a `Map<TreeNode, int[]>` to store `[subtree_size, subtree_coin_sum]` for each node.
- Implement a post-order DFS function `gatherInfo(node)`:
  - If `node` is null, return `[0, 0]`.
  - Recursively call `gatherInfo` for left and right children to get `[left_size, left_coins]` and `[right_size, right_coins]`.
  - Calculate `current_size = 1 + left_size + right_size` and `current_coins = node.val + left_coins + right_coins`.
  - Store `[current_size, current_coins]` in the map for the current `node`.
  - Return `[current_size, current_coins]`.
- Call `gatherInfo(root)` to populate the map.
- Initialize `total_moves = 0`.
- Iterate through the values in the map. For each `info` array `[size, coins]`, add `abs(coins - size)` to `total_moves`.
- Return `total_moves`.

## Single-Pass Post-Order Traversal (DFS)
This is the most efficient approach, solving the problem in a single post-order traversal (DFS). The key insight is to consider the 'balance' of coins at each subtree. The balance is the number of coins a subtree has minus the number of nodes it contains. A positive balance means the subtree has an excess of coins that must be passed up to its parent. A negative balance means it has a deficit and needs coins from its parent. The number of moves across the edge to the parent is the absolute value of this balance. By recursively calculating this balance from the leaves up to the root, we can sum the moves required at each edge.
**Time:** O(N), where N is the number of nodes in the tree. The DFS-based approach visits each node exactly once. · **Space:** O(H), where H is the height of the tree. This space is used by the recursion stack. In the worst case of a skewed tree, H can be equal to N, leading to O(N) space. For a balanced tree, the space complexity is O(log N).
**Pros:** Highly efficient in both time and space.; Solves the problem in a single pass over the tree.; Elegant and concise solution.
**Cons:** The concept of returning a 'balance' might be slightly less intuitive at first glance compared to a two-pass approach where data gathering and calculation are separate.
### Explanation
We can solve this problem efficiently with a single pass using a post-order traversal. We define a recursive function, let's call it `dfs(node)`, which serves two purposes: it calculates the total moves and it returns the coin balance of the subtree rooted at `node`.

The coin balance is `(total_coins_in_subtree) - (total_nodes_in_subtree)`. 
- If the balance is `+k`, it means the subtree has an excess of `k` coins, which need to be moved out (up to the parent). This requires `k` moves across the parent-child edge.
- If the balance is `-k`, it means the subtree has a deficit of `k` coins, which need to be moved in (from the parent). This also requires `k` moves.

In either case, the number of moves associated with the edge connecting a child's subtree to its parent is the absolute value of the child's subtree balance.

Our `dfs(node)` function works as follows:
1. It recursively calls itself on the left and right children, receiving their balances (`leftBalance`, `rightBalance`).
2. The moves required to satisfy these children are `abs(leftBalance)` and `abs(rightBalance)`. We add these to a global `moves` counter.
3. The balance for the current node's subtree is its own coin excess/deficit (`node.val - 1`) plus the balances from its children (`leftBalance + rightBalance`).
4. This new balance is returned up to its caller (the parent node).

By the time the traversal completes at the root, the `moves` counter will hold the total minimum number of moves.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int moves = 0;

    public int distributeCoins(TreeNode root) {
        dfs(root);
        return moves;
    }

    /**
     * Performs a post-order traversal.
     * Returns the balance of coins for the subtree rooted at 'node'.
     * Balance = (number of coins in subtree) - (number of nodes in subtree).
     * A positive balance means an excess of coins to be moved up.
     * A negative balance means a deficit of coins to be moved down.
     */
    private int dfs(TreeNode node) {
        if (node == null) {
            return 0;
        }

        // Recursively calculate the balance of left and right subtrees.
        int leftBalance = dfs(node.left);
        int rightBalance = dfs(node.right);

        // The number of moves is the sum of coins that need to cross each edge.
        // The number of coins crossing the edge from a child to the parent
        // is the absolute value of the child's subtree balance.
        moves += Math.abs(leftBalance) + Math.abs(rightBalance);

        // The balance for the current node's subtree.
        // It has node.val coins, needs 1, and gets/gives coins from/to its children.
        return node.val - 1 + leftBalance + rightBalance;
    }
}
```
### Algorithm
- Initialize a variable `total_moves = 0` (e.g., as a class member).
- Implement a post-order DFS function `dfs(node)` that returns the coin balance of the subtree.
- **Base Case**: If `node` is null, return 0.
- **Recursive Step**:
  - Recursively call `dfs` for the left child: `left_balance = dfs(node.left)`.
  - Recursively call `dfs` for the right child: `right_balance = dfs(node.right)`.
- **Process Node**:
  - The number of moves across the edges to the children are `abs(left_balance)` and `abs(right_balance)`. Add these to `total_moves`.
  - Calculate the balance for the current subtree: `current_balance = node.val - 1 + left_balance + right_balance`.
  - Return `current_balance`.
- Call `dfs(root)` to start the process. The final answer is the accumulated value in `total_moves`.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private int ans ; public int distributeCoins ( TreeNode root ) { dfs ( root ); return ans ; } private int dfs ( TreeNode root ) { if ( root == null ) { return 0 ; } int left = dfs ( root . left ); int right = dfs ( root . right ); ans += Math . abs ( left ) + Math . abs ( right ); return left + right + root . val - 1 ; } }
```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int distributeCoins ( TreeNode * root ) { int ans = 0 ; function < int ( TreeNode * ) > dfs = [ & ]( TreeNode * root ) -> int { if ( ! root ) { return 0 ; } int left = dfs ( root -> left ); int right = dfs ( root -> right ); ans += abs ( left ) + abs ( right ); return left + right + root -> val - 1 ; }; dfs ( root ); return ans ; } };
```

### Python

```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 : def dfs ( root ): if root is None : return 0 left , right = dfs ( root . left ), dfs ( root . right ) nonlocal ans ans += abs ( left ) + abs ( right ) return left + right + root . val - 1 ans = 0 dfs ( root ) return ans
```