Code 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: TreeNode) -> int:
        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
      

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int moves = 0;
    int dfs(TreeNode* node) {
        if (!node) return 0;
        int left = dfs(node->left);
        int right = dfs(node->right);
        moves += abs(left) + abs(right);
        return node->val + left + right - 1;
    }
    int distributeCoins(TreeNode* root) {
        moves = 0;
        dfs(root);
        return moves;
    }
};
      

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

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var distributeCoins = function(root) {
    let moves = 0;
    function dfs(node) {
        if (!node) return 0;
        let left = dfs(node.left);
        let right = dfs(node.right);
        moves += Math.abs(left) + Math.abs(right);
        return node.val + left + right - 1;
    }
    dfs(root);
    return moves;
};
      

Problem Description

You are given the root of a binary tree where each node has an integer value representing the number of coins at that node. There are exactly n nodes and exactly n coins in total.

In one move, you can choose any node and move one coin from it to its parent or to one of its children. You can make as many moves as you want, but each move must transfer only a single coin to an adjacent node (parent or child).

The goal is to make every node in the tree have exactly 1 coin. Return the minimum number of moves required to achieve this.

• There is always exactly one valid solution.
• Each move can only transfer a coin between directly connected nodes (no skipping nodes).
• Nodes may have more than one coin initially, or zero coins.

Thought Process

At first glance, this problem seems to require simulating all possible moves between nodes to balance the coins. However, simulating every possible move would be extremely inefficient, especially for larger trees.

Let's think about what it means for a node to have too many or too few coins. If a node has more than one coin, it must send the extra coins to its parent or children. If it has fewer than one, it must receive coins from its parent or children. The minimum number of moves is determined by the total number of coins that need to be moved across edges to reach the balanced state.

This leads to the insight that we can process the tree in a bottom-up fashion (postorder traversal), calculating for each node how many coins it needs to send or receive. For each node, we can sum the absolute values of coins that need to be moved from its left and right subtrees, and propagate the net coin balance up to its parent.

Instead of brute-force simulation, we can use recursion to efficiently compute the total moves required.

Solution Approach

The optimal solution uses a recursive depth-first search (DFS) traversal in postorder (left, right, root). Here's how it works step by step:

1. Define the recursive function: For each node, calculate the net number of coins that need to be sent to (or received from) its parent. This is done by:
   • Recursively solving for the left and right subtrees.
   • Calculating the net coins at this node: node.val + left + right - 1. The -1 accounts for the fact that the node itself needs to keep exactly one coin.
2. Count the moves: For each node, add abs(left) + abs(right) to a global move counter. This represents the total number of coins moved in or out of the left and right subtrees.
3. Propagate the balance: Return the net balance to the parent, which will be handled at the next level up the tree.
4. Start the recursion at the root: The final answer will be the accumulated moves counter.

This approach ensures that every coin movement is counted exactly once, and the recursion efficiently computes the minimum moves required.

Example Walkthrough

Consider the following binary tree:

         3
        / \
       0   0
  

• The root has 3 coins, its left and right children have 0 coins each.
• We want each node to have 1 coin.

Let's walk through the algorithm:

1. Start at the left child (value 0):
   • Left and right children are null, so their balances are 0.
   • Net balance = 0 + 0 + 0 - 1 = -1 (needs 1 coin from parent).
   • Moves so far: 0.
2. Right child (value 0): Same as left, net balance = -1, moves so far: 0.
3. Root (value 3):
   • Left balance = -1, right balance = -1.
   • Add abs(-1) + abs(-1) = 2 moves (one coin to each child).
   • Net balance = 3 + (-1) + (-1) - 1 = 0.
4. The recursion ends. Total moves required: 2.

This matches the minimal number of moves: move one coin from root to left child, one coin from root to right child.

Time and Space Complexity

• Brute-force approach: If we tried all possible move sequences, the time complexity would be exponential, as there are many ways to move coins between nodes.
• Optimized approach (DFS):
  • Time Complexity: O(n), where n is the number of nodes. We visit each node exactly once and perform constant work per node.
  • Space Complexity: O(h), where h is the height of the tree (due to the recursion stack). For a balanced tree, this is O(log n); for a skewed tree, O(n).

Summary

The "Distribute Coins in Binary Tree" problem is elegantly solved by a single postorder DFS traversal. By treating each node's coin surplus or deficit as a value to be propagated up the tree, we can count the minimum moves required in a single pass. The key insight is that the number of moves is determined by the absolute value of coins transferred between each node and its children. This approach is both efficient and intuitive, leveraging recursive thinking and the properties of trees.