Domain 2MediumMEDIUM

Distribute Coins in Binary Tree

Calculate minimum moves to balance coins in a binary tree using post-order DFS, tracking subtree surplus/deficit flow across edges.

Domain: medium•Updated: 2026-09-05
#Depth-First Search#Binary Tree#O(N)#O(H)

Problem Breakdown

We are given the root of a binary tree where each node has node.val coins. The total number of nodes equals the sum of all coin values (n). We need to redistribute these coins so that every node ends up with exactly one coin using adjacent moves (parent-child). Each move transfers one coin between two connected nodes.

Inputs:

  • Root of a Binary Tree (TreeNode) where node.val represents initial coins at that node.

Outputs:

  • Integer representing the total number of moves required to balance all nodes.

Constraints & Edge Cases:

  • 1≤n≤1001 \le n \le 100: Small input size ensures recursion is safe from stack overflow (standard limit ~1000).
  • sum(Node.val) == n: Guarantees a valid solution exists; no need to validate total coin count.
  • Empty tree: Constraints state n≥1n \ge 1, so root always exists, but recursive logic must handle null children gracefully.

Intuition

A naive simulation of moving coins one by one is inefficient (O(N2)O(N^2) or worse) because we don’t know the optimal path without analyzing subtree balances first. Instead, consider any node and its descendants as a self-contained unit (a subtree).

Key Insight: The movement of coins across an edge connecting a child to its parent depends on whether that child’s subtree has excess coins or needs more coins relative to the number of nodes in it.

  1. Excess Flow Up: If a subtree rooted at child contains XX coins and YY nodes (X>YX > Y), there is an excess of (X−Y)(X - Y) coins that must move up to the parent node. Each coin crossing this edge counts as one move.
  2. Deficit Flow Down: If a subtree has fewer coins than nodes, it needs to pull from the parent. The deficit amount represents moves flowing down across that specific edge.

Therefore, for every node processed in a bottom-up traversal (Post-Order DFS), we calculate its “net balance” relative to itself and all descendants: (sum of coin values) - (number of nodes).

  • If balance > 0: Excess flows up. Cost = balance.
  • If balance < 0: Deficit needs filling from parent. Cost = abs(balance).

We accumulate these costs globally to find the total moves required.

Approach

  1. Initialize a counter for total_moves (using closure or class attribute).
  2. Define a recursive helper function dfs(node) that returns an integer: the net coin surplus/deficit of the subtree rooted at node.
  3. Base Case: If node is null, return 0 balance. This signifies no coins and no nodes in this branch.
  4. Recursive Step (Post-Order):
    • Recursively call dfs on left and right children to get their balances (left_balance, right_balance). These values represent the net flow required from/to those subtrees relative to themselves.
    • Add the absolute values of these child balances to our global total_moves. This accounts for coins moving across edges between current node and its immediate children (flowing up or down).
    • Calculate the new balance for the current subtree: (node.val - 1) + left_balance + right_balance. We subtract 1 because every single node in this subtree needs exactly one coin to be satisfied. The val is what we have, -1 is what that specific node consumes/needs locally.
  5. Return the calculated net balance for the current subtree up to its parent call.

Complexity Analysis

  • Time: O(N)O(N) where NN is the number of nodes in the tree. We visit each node exactly once during the DFS traversal. Operations per node are constant time arithmetic additions/subtractions/abs calls.
  • Space: O(H)O(H) for recursion stack space, where HH is the height of the tree. In a skewed tree (worst case), this becomes O(N)O(N). Given constraints (N≤100N \le 100), this overhead is negligible and well within standard limits.

Solution

# 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:
        # Use a nonlocal variable to accumulate moves within the nested function scope.
        total_moves = 0
        
        def dfs(node):
            if not node:
                return 0
            
            left_balance = dfs(node.left)
            right_balance = dfs(node.right)
            
            # Add moves required to balance the edges between this node and its children.
            # If a child has excess, it flows up (cost). 
            # If a child needs coins, they flow down from here (cost).
            total_moves += abs(left_balance) + abs(right_balance)
            
            # Calculate net surplus/deficit for the current subtree including this node.
            # We subtract 1 because every node in this subtree must hold exactly one coin eventually.
            return (node.val - 1) + left_balance + right_balance
        
        dfs(root)
        
        return total_moves

# Example usage:
# root = [3,0,0] -> Output: 2

Edge Cases Handled

  • Single Node Tree: dfs returns (val-1) (which is 0 if val=1). Moves remain 0. Correct since a single node with 1 coin needs no moves. If it had >1 coins, the logic would still hold but constraints say sum of vals == n and n >= 1 implies valid distribution exists eventually.
  • Deep Skewed Trees: Recursion handles depth up to NN. Python recursion limit usually allows ~1000, sufficient for $N \le 100`.
  • Zero Coins at Leaves: Returns negative balance (deficit), correctly adding abs moves when parent processes it.
  • Root with All Coins: Children return deficits, root accumulates excess and returns positive flow up to null (ignored). Moves counted during child processing are correct as they represent the actual transfers needed across edges.