LeetCode 979 - Distribute Coins in Binary Tree

In this problem, we are given a binary tree where every node contains some number of coins. The total number of coins across the entire tree is exactly equal to the number of nodes in the tree.

leetcodemediumtreedepth-first-searchbinary-tree

LeetCode Problem 979

Difficulty: 🟡 Medium
Topics: Tree, Depth-First Search, Binary Tree

Solution

Problem Understanding

In this problem, we are given a binary tree where every node contains some number of coins. The total number of coins across the entire tree is exactly equal to the number of nodes in the tree. Our goal is to redistribute the coins so that every node ends up with exactly one coin.

A single move consists of transferring one coin between two adjacent nodes. Since the tree is undirected in terms of movement, a coin can move from a parent to a child or from a child to a parent. Every edge traversal by a single coin counts as one move.

The challenge is to determine the minimum number of moves required to make the distribution balanced.

The input is the root of a binary tree. Each node has:

  • node.val, representing how many coins the node currently holds
  • left and right pointers to its children

The output is a single integer representing the minimum number of coin transfers required.

The constraints are small:

  • The tree contains at most 100 nodes
  • Each node can contain between 0 and n coins
  • The total number of coins always equals the total number of nodes

These constraints tell us that even an O(n^2) solution could technically pass, but the structure of the problem strongly suggests that a linear traversal is possible.

There are several important edge cases:

  • A node may already have exactly one coin, requiring no movement.
  • A node may have zero coins and depend entirely on incoming transfers.
  • A node may contain many excess coins that must be distributed upward and downward.
  • The tree may be highly unbalanced, effectively becoming a linked list.
  • The root itself may need to send or receive many coins.

A naive implementation can easily miscount moves if it does not properly account for how many coins flow across each edge.

Approaches

Brute Force Approach

A brute force strategy would repeatedly search for nodes with excess coins and move coins toward nodes that are missing coins.

One possible implementation is:

  1. Find a node with more than one coin.
  2. Find the nearest node with zero coins.
  3. Move coins along the path between them.
  4. Repeat until every node contains one coin.

This eventually produces a correct result because every move gradually reduces imbalance. However, it is inefficient because each redistribution may require traversing large parts of the tree to locate deficits and compute paths.

The major issue is that the same edges may be traversed repeatedly. In the worst case, each redistribution operation costs O(n), and we may need O(n) redistributions, leading to O(n^2) complexity.

More importantly, the brute force method does not naturally expose the key structure of the problem, which is that each subtree can independently determine how many coins it must send or receive.

Key Insight for the Optimal Solution

The crucial observation is that every subtree has a natural "coin balance."

For any subtree:

  • If it contains more coins than nodes, it has excess coins to give away.
  • If it contains fewer coins than nodes, it needs coins from its parent.

Suppose a subtree contains:

  • totalCoins coins
  • totalNodes nodes

Then its balance is:

balance = totalCoins - totalNodes

This balance tells us:

  • Positive balance, subtree sends coins upward
  • Negative balance, subtree receives coins from parent
  • Zero balance, subtree is already internally balanced

The number of moves contributed by a subtree is simply the absolute value of the balance transferred across the edge connecting it to its parent.

This naturally suggests a postorder depth-first traversal:

  1. Solve left subtree.
  2. Solve right subtree.
  3. Compute current node balance.
  4. Add the amount of transferred coins to the answer.

Because every edge is processed exactly once, the solution becomes linear.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Repeatedly searches and redistributes coins
Optimal DFS O(n) O(h) Postorder traversal computes subtree balances efficiently

Here, h represents the height of the tree.

Algorithm Walkthrough

Optimal Postorder DFS Algorithm

  1. Perform a postorder depth-first traversal of the tree.

We process children before the parent because the parent needs to know how many excess or missing coins each subtree has. 2. Recursively compute the balance of the left subtree.

The returned value represents how many coins the left subtree sends to its parent:

  • Positive means excess coins
  • Negative means missing coins
  1. Recursively compute the balance of the right subtree.

This is handled exactly the same way. 4. Count the moves needed for both subtrees.

Every coin crossing an edge costs one move. Therefore:

moves += abs(leftBalance) + abs(rightBalance)

The absolute value is important because both sending and receiving require movement across the edge. 5. Compute the current node's balance.

The node contributes:

  • node.val coins
  • Needs exactly one coin for itself

Therefore:

currentBalance = node.val + leftBalance + rightBalance - 1
  1. Return the balance upward.

The parent will use this balance to determine how many coins move across the connecting edge.

Why It Works

The algorithm works because every subtree independently determines its surplus or deficit relative to the number of nodes it contains.

Any imbalance must cross exactly one edge, the edge connecting the subtree to its parent. Therefore, the minimum number of moves contributed by that subtree is exactly the absolute value of its balance.

Since every edge is processed once during postorder traversal, and every necessary coin transfer is counted exactly once, the algorithm produces the minimum possible number of moves.

Python 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

from typing import Optional

class Solution:
    def distributeCoins(self, root: Optional[TreeNode]) -> int:
        moves = 0

        def dfs(node: Optional[TreeNode]) -> int:
            nonlocal moves

            if not node:
                return 0

            left_balance = dfs(node.left)
            right_balance = dfs(node.right)

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

            current_balance = (
                node.val + left_balance + right_balance - 1
            )

            return current_balance

        dfs(root)

        return moves

The implementation follows the postorder traversal strategy directly.

The dfs function returns the balance of the current subtree. A positive value means the subtree has extra coins to send upward, while a negative value means it needs coins from its parent.

The recursion first processes the left and right subtrees. Once their balances are known, we know exactly how many coins must cross the edges connecting them to the current node.

The statement:

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

counts all coin transfers across those edges.

Finally, the current node computes its own balance by combining:

  • Its own coins
  • The balances from both children
  • The one coin it must keep for itself

The final answer accumulates in moves.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func distributeCoins(root *TreeNode) int {
    moves := 0

    var dfs func(node *TreeNode) int

    dfs = func(node *TreeNode) int {
        if node == nil {
            return 0
        }

        leftBalance := dfs(node.Left)
        rightBalance := dfs(node.Right)

        moves += abs(leftBalance) + abs(rightBalance)

        currentBalance := node.Val + leftBalance + rightBalance - 1

        return currentBalance
    }

    dfs(root)

    return moves
}

func abs(x int) int {
    if x < 0 {
        return -x
    }

    return x
}

The Go solution mirrors the Python implementation closely.

The primary difference is that Go does not provide a built-in integer absolute value function for generic integers, so we define a helper abs function.

Go also uses explicit nil checks instead of Python's truthiness checks. Otherwise, the recursive logic and balance calculations remain identical.

Worked Examples

Example 1

Input: [3,0,0]

      3
     / \
    0   0

Step-by-Step Traversal

Node Left Balance Right Balance Moves Added Current Balance
Left child (0) 0 0 0 -1
Right child (0) 0 0 0 -1
Root (3) -1 -1 2 0

Explanation

The left child needs one coin, so it returns -1.

The right child also needs one coin, so it returns -1.

The root has 3 coins. It gives one coin to each child:

3 + (-1) + (-1) - 1 = 0

Total moves:

abs(-1) + abs(-1) = 2

Final answer:

2

Example 2

Input: [0,3,0]

      0
     / \
    3   0

Step-by-Step Traversal

Node Left Balance Right Balance Moves Added Current Balance
Left child (3) 0 0 0 2
Right child (0) 0 0 0 -1
Root (0) 2 -1 3 0

Explanation

The left child has 3 coins but only needs 1, so it returns 2.

The right child has no coins and needs one, so it returns -1.

The root receives 2 coins from the left and sends 1 coin to the right.

Moves added:

abs(2) + abs(-1) = 3

Final answer:

3

Complexity Analysis

Measure Complexity Explanation
Time O(n) Every node is visited exactly once
Space O(h) Recursive call stack depth equals tree height

The DFS traversal processes each node a single time and performs only constant work per node, resulting in linear time complexity.

The space complexity comes from recursion depth. In a balanced tree, this is O(log n), while in the worst case of a skewed tree, it becomes O(n).

Test Cases

# Definition for testing
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):
        moves = 0

        def dfs(node):
            nonlocal moves

            if not node:
                return 0

            left = dfs(node.left)
            right = dfs(node.right)

            moves += abs(left) + abs(right)

            return node.val + left + right - 1

        dfs(root)

        return moves

sol = Solution()

# Example 1
root = TreeNode(3, TreeNode(0), TreeNode(0))
assert sol.distributeCoins(root) == 2  # Simple balanced redistribution

# Example 2
root = TreeNode(0, TreeNode(3), TreeNode(0))
assert sol.distributeCoins(root) == 3  # Coins must move through root

# Single node already balanced
root = TreeNode(1)
assert sol.distributeCoins(root) == 0  # No moves needed

# Left-skewed tree
root = TreeNode(0,
    TreeNode(0,
        TreeNode(3)
    )
)
assert sol.distributeCoins(root) == 3  # Moves along chain

# Right-skewed tree
root = TreeNode(3,
    None,
    TreeNode(0,
        None,
        TreeNode(0)
    )
)
assert sol.distributeCoins(root) == 3  # Redistribution down chain

# Complex balanced case
root = TreeNode(1,
    TreeNode(0, TreeNode(3), None),
    TreeNode(0)
)
assert sol.distributeCoins(root) == 4  # Multiple subtree transfers

# All nodes already correct
root = TreeNode(1,
    TreeNode(1),
    TreeNode(1)
)
assert sol.distributeCoins(root) == 0  # Already balanced

print("All tests passed!")

Test Summary

Test Why
[3,0,0] Basic redistribution from root
[0,3,0] Coins must travel through parent
[1] Smallest valid input
Left-skewed tree Tests deep recursive propagation
Right-skewed tree Tests unbalanced tree handling
Complex mixed tree Validates multiple simultaneous imbalances
Already balanced tree Ensures zero unnecessary moves

Edge Cases

Single Node Tree

A tree containing only one node with one coin is already balanced. This case is important because recursive algorithms sometimes incorrectly count moves or mishandle leaf nodes.

The implementation handles this naturally. The DFS returns a balance of zero, and no moves are added.

Highly Skewed Tree

A tree shaped like a linked list can create deep recursive paths. This is important because coin transfers may need to propagate across many edges.

The implementation correctly processes balances bottom-up, ensuring every edge transfer is counted exactly once regardless of tree shape.

Nodes with Large Coin Excess

A node may contain many more coins than necessary. For example, one node could contain all n coins while every other node contains zero.

This can be tricky because multiple transfers must propagate through intermediate nodes. The algorithm handles this elegantly because balances naturally accumulate and propagate upward through recursion.

Already Balanced Subtrees

Some subtrees may already contain exactly the right number of coins internally.

A buggy implementation might still count unnecessary movements. In this solution, balanced subtrees return a balance of zero, meaning no moves are added for their parent edge.