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.
To solve the problem, we perform a post-order traversal of the tree. During this traversal, for each node, we calculate the excess coins (i.e., the number of coins - 1) that need to be moved either up to the parent or down to the children. We accumulate the absolute values of excess coins for each move.
This code defines a binary tree node with a value and optional left and right children. The distributeCoins function calculates the minimum number of moves needed to distribute coins such that each node has exactly one coin. The dfs helper function calculates the excess coins at each node using post-order traversal and updates the global count of moves.
Python
Java
C++
C#
JavaScript
Time Complexity: O(n), where n is the number of nodes in the tree. We visit each node exactly once.
Space Complexity: O(h), where h is the height of the tree due to the recursion stack.
We define a function dfs(node), which represents the coin overload in the subtree rooted at node, i.e., the number of coins minus the number of nodes. If dfs(node) is positive, it means the subtree has more coins than nodes, and the excess coins need to be moved out of the subtree; if dfs(node) is negative, it means the subtree has fewer coins than nodes, and the shortfall needs to be moved into the subtree.
In the function dfs(node), we first traverse the left and right subtrees to obtain the coin overload left and right of the left and right subtrees, respectively. Then, the current number of moves needs to be increased by |left| + |right|, which means moving the coins from the left and right subtrees to the current node. After that, we return the coin overload of the entire subtree, which is left + right + node.val - 1.
Finally, we return the number of moves.
The time complexity is O(n), and the space complexity is O(h). Here, n and h respectively represent the number of nodes and the height of the binary tree.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Post-order Traversal to Calculate Excess Coins | Time Complexity: O(n), where n is the number of nodes in the tree. We visit each node exactly once. |
| DFS | — |
| 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 |
LeetCode Distribute Coins in a Binary Tree Explained - Java • Nick White • 21,968 views views
Watch 9 more video solutions →Practice Distribute Coins in Binary Tree with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor