Watch 10 video solutions for Distribute Coins in Binary Tree, a medium level problem involving Tree, Depth-First Search, Binary Tree. This walkthrough by Nick White has 21,968 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
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:
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:
n.1 <= n <= 1000 <= Node.val <= nNode.val is n.Problem Overview: Each node in a binary tree contains some coins, and the total number of coins equals the total number of nodes. The goal is to move coins along edges so every node ends up with exactly one coin while minimizing the number of moves.
Approach 1: Repeated Redistribution Simulation (O(n^2) time, O(h) space)
A straightforward idea is to repeatedly scan the tree and move coins between parents and children whenever a node has more than one coin or zero coins. Each pass attempts to balance local imbalances until every node has exactly one coin. This approach works but becomes inefficient because each redistribution may require multiple full traversals of the tree. In the worst case, every adjustment propagates across many nodes, leading to O(n^2) time complexity with recursion stack space O(h), where h is the tree height. It helps build intuition about coin flow but is rarely used in production or interviews.
Approach 2: Post-order Traversal to Calculate Excess Coins (O(n) time, O(h) space)
The optimal solution performs a post-order traversal of the binary tree. Each recursive call returns the excess coins from that subtree: excess = node.val + left_excess + right_excess - 1. A positive value means the subtree has extra coins to send upward, while a negative value means it needs coins from the parent. The number of moves contributed by a node equals abs(left_excess) + abs(right_excess), because every surplus or deficit must travel across the edge connecting that subtree.
This works because every coin movement corresponds exactly to an imbalance detected during the DFS. By aggregating excess values from children before processing the parent, the algorithm naturally models how coins flow through edges. The traversal touches each node once, giving O(n) time complexity and O(h) recursion space. The technique relies on a classic depth-first search pattern applied to a tree structure.
Recommended for interviews: The post-order DFS approach is the expected solution. Interviewers want to see that you model the problem as a flow of excess coins between subtrees and compute moves during traversal. Mentioning the naive redistribution idea shows problem exploration, but implementing the O(n) DFS solution demonstrates strong tree and recursion fundamentals.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Repeated Redistribution Simulation | O(n^2) | O(h) | Conceptual understanding of how coins propagate across edges |
| Post-order Traversal to Calculate Excess Coins | O(n) | O(h) | Optimal solution for interviews and production; processes each node once |