Distribute Coins in Binary Tree — Problem & Solution
Distribute Coins in Binary Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Distribute Coins in Binary Tree is a medium coding problem on depth-first search and trees, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Medium
- Topics: Depth-First Search, Trees
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given the root of a binary tree with n nodes, where node.val is the number of coins on that node. There are exactly n coins in the whole tree.
In one move you may take one coin from a node and move it to an adjacent node — its parent or one of its children. Return the minimum number of moves needed so that every node holds exactly one coin.
Example 1
Input: root = [3,0,0]
Output: 2
Explanation: The root sends one coin to each child: 2 moves.
Example 2
Input: root = [0,3,0]
Output: 3
Explanation: The left child sends one coin up to the root and another up and then down to the right child: 1 + 2 = 3 moves.
Example 3
Input: root = [1,0,0,null,3]
Output: 4
Explanation: Node 3 passes two coins up to its parent (2 moves), which keeps one and passes the other up to the root (1 move); the root keeps its own coin and passes the arriving one down to its right child (1 move). 4 moves in all.
Constraints
The number of nodes in the tree is n1 <= n <= 1000 <= Node.val <= nThe sum of all Node.val is n
Hints for Distribute Coins in Binary Tree
Hint 1
Look at a single edge between a node and its parent. How many coins must cross it, in total, whatever else happens?
Hint 2
The subtree below the edge holds some number of coins and needs exactly as many as it has nodes. The difference — its excess, positive or negative — must cross that edge, and never more than that.
Hint 3
A post-order DFS can return each subtree's excess (
coins − nodes); the answer is the sum of|excess|over all edges.
How to solve Distribute Coins in Binary Tree
Each edge must carry exactly the imbalance of the subtree below it, and an optimal schedule never moves a coin across an edge in both directions. So the minimum is the sum, over every edge, of the absolute excess of the subtree it leads to.
Approach
excess(node): 0 for null. Otherwise computel = excess(left)andr = excess(right).- Add
|l| + |r|to the move count — those many coins cross the two child edges. - Return
node.val + l + r - 1: the coins this subtree has minus the one this node keeps (negative means it needs coins from above). - Call
excess(root)(the root's own excess is 0) and return the move count.
Why it works
Any valid plan must move at least |excess| coins across an edge, since the subtree below ends with exactly as many coins as nodes. Moving surplus up and deficits down along each edge achieves exactly that many crossings per edge, so the lower bound is met.
Complexity
- Time —
O(n) - Space —
O(h) for the recursion
Pitfalls
- Excess can be negative — count its absolute value as moves, but pass the signed value up.
- Count moves on child edges only; the root has no parent edge.
Reference solution
Python
from typing import Optional
def distributeCoins(root: Optional[TreeNode]) -> int:
moves = 0
def excess(node):
nonlocal moves
if node is None:
return 0
l = excess(node.left)
r = excess(node.right)
moves += abs(l) + abs(r)
return node.val + l + r - 1
excess(root)
return movesJava
public static int distributeCoins(TreeNode root) {
int[] moves = new int[1];
excess(root, moves);
return moves[0];
}
static int excess(TreeNode node, int[] moves) {
if (node == null) return 0;
int l = excess(node.left, moves), r = excess(node.right, moves);
moves[0] += Math.abs(l) + Math.abs(r);
return node.val + l + r - 1;
}C++
int coinExcess(TreeNode* node, int& moves);
int distributeCoins(TreeNode* root) {
int moves = 0;
coinExcess(root, moves);
return moves;
}
int coinExcess(TreeNode* node, int& moves) {
if (!node) return 0;
int l = coinExcess(node->left, moves), r = coinExcess(node->right, moves);
moves += abs(l) + abs(r);
return node->val + l + r - 1;
}JavaScript
var distributeCoins = function(root) {
var moves = 0;
var excess = function(node) {
if (node === null) return 0;
var l = excess(node.left), r = excess(node.right);
moves += Math.abs(l) + Math.abs(r);
return node.val + l + r - 1;
};
excess(root);
return moves;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals