Distribute Coins in Binary Tree
Distribute Coins in Binary Tree is a medium trees & bst problem solved with the postorder + multiple return values pattern.
The best approach, optimal (postorder excess), runs in O(n) time and O(h) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (count each edge separately) up.
Problem
You are given the root of a binary tree with n nodes. Node values are coin counts, and there are exactly n coins in the whole tree, though some nodes may hold several and others none.
In one move you take a single coin from a node and hand it to a neighbouring node (its parent or one of its children). Return the minimum number of moves needed so that every node ends up with exactly one coin.
Examples
Example 1
- Input
root = [0, 3, 0]- Output
3- Why
- The left child sends two coins up to the root (2 moves), then the root passes one coin down to the right child (1 move).
Example 2
- Input
root = [1, 0, 2]- Output
2- Why
- The extra coin on the right travels to the root and then to the left child.
Example 3
- Input
root = [0, 0, null, 3]- Output
3- Why
- The bottom node sends 2 coins up one edge; the middle node then sends 1 of them up to the root.
Constraints
- The tree has
nnodes,1 <= n <= 100. 0 <= Node.val <= n- The values add up to exactly
n.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (count each edge separately) | O(n²) | O(h) |
| Optimal (postorder excess) | O(n) | O(h) |
1Brute force (count each edge separately)
O(n²)Each of the n nodes sums its own subtree again, up to n work per node on a chain.O(h)Recursion stack of the tree height h.Every edge from a node to its parent is crossed exactly |coins in subtree - nodes in subtree| times. For every node, count the coins and nodes of its subtree from scratch and add that amount.
coins(n)andsize(n)are plain recursive sums.- For each non-root node add
|coins(n) - size(n)|. - Visit every node with a separate traversal.
class Solution {
public int distributeCoins(TreeNode root) {
return edges(root.left) + edges(root.right);
}
private int edges(TreeNode n) {
if (n == null) return 0;
int here = Math.abs(coins(n) - size(n));
return here + edges(n.left) + edges(n.right);
}
private int coins(TreeNode n) {
return n == null ? 0 : n.val + coins(n.left) + coins(n.right);
}
private int size(TreeNode n) {
return n == null ? 0 : 1 + size(n.left) + size(n.right);
}
}class Solution:
def distributeCoins(self, root: Optional[TreeNode]) -> int:
return self.edges(root.left) + self.edges(root.right)
def edges(self, n: Optional[TreeNode]) -> int:
if n is None:
return 0
here = abs(self.coins(n) - self.size(n))
return here + self.edges(n.left) + self.edges(n.right)
def coins(self, n: Optional[TreeNode]) -> int:
return 0 if n is None else n.val + self.coins(n.left) + self.coins(n.right)
def size(self, n: Optional[TreeNode]) -> int:
return 0 if n is None else 1 + self.size(n.left) + self.size(n.right)class Solution {
public:
int distributeCoins(TreeNode* root) {
return edges(root->left) + edges(root->right);
}
private:
int edges(TreeNode* n) {
if (n == nullptr) return 0;
int here = abs(coins(n) - size(n));
return here + edges(n->left) + edges(n->right);
}
int coins(TreeNode* n) {
return n == nullptr ? 0 : n->val + coins(n->left) + coins(n->right);
}
int size(TreeNode* n) {
return n == nullptr ? 0 : 1 + size(n->left) + size(n->right);
}
};function distributeCoins(root) {
return edges(root.left) + edges(root.right);
}
function edges(n) {
if (n === null) return 0;
const here = Math.abs(coins(n) - size(n));
return here + edges(n.left) + edges(n.right);
}
function coins(n) {
return n === null ? 0 : n.val + coins(n.left) + coins(n.right);
}
function size(n) {
return n === null ? 0 : 1 + size(n.left) + size(n.right);
}2Optimal (postorder excess)
O(n)Each node is visited once.O(h)Recursion depth equals the tree height.Let excess(n) = coins in the subtree minus nodes in the subtree. A positive excess means that many coins must go up to the parent, a negative one means that many must come down. One postorder pass returns the excess and adds |excess| of each child to the move count.
excess(null) = 0.l = excess(left),r = excess(right).moves += |l| + |r|.- Return
n.val + l + r - 1(the node keeps one coin for itself).
class Solution {
private int moves;
public int distributeCoins(TreeNode root) {
moves = 0;
excess(root);
return moves;
}
private int excess(TreeNode n) {
if (n == null) return 0;
int l = excess(n.left), r = excess(n.right);
moves += Math.abs(l) + Math.abs(r);
return n.val + l + r - 1;
}
}class Solution:
def distributeCoins(self, root: Optional[TreeNode]) -> int:
self.moves = 0
self.excess(root)
return self.moves
def excess(self, n: Optional[TreeNode]) -> int:
if n is None:
return 0
l, r = self.excess(n.left), self.excess(n.right)
self.moves += abs(l) + abs(r)
return n.val + l + r - 1class Solution {
public:
int distributeCoins(TreeNode* root) {
moves = 0;
excess(root);
return moves;
}
private:
int moves;
int excess(TreeNode* n) {
if (n == nullptr) return 0;
int l = excess(n->left), r = excess(n->right);
moves += abs(l) + abs(r);
return n->val + l + r - 1;
}
};function distributeCoins(root) {
let moves = 0;
function excess(n) {
if (n === null) return 0;
const l = excess(n.left), r = excess(n.right);
moves += Math.abs(l) + Math.abs(r);
return n.val + l + r - 1;
}
excess(root);
return moves;
}Edge cases to test
- Every node already holds one coin: 0 moves
- All coins sit on one leaf and must travel across the whole tree
- A single node with one coin
- Coins must pass through a node that itself has zero coins
Hints
Hint 1
Look at one edge between a node and its parent. How many coins must cross it, no matter how you schedule the moves?
Hint 2
If a subtree holds c coins and has s nodes, exactly |c - s| coins cross the edge above it.
Hint 3
Let a postorder pass return coins - nodes (the excess) of each subtree, and add the absolute value of each child's excess to the answer.
FAQ
What is the best time complexity for Distribute Coins in Binary Tree?
Optimal (postorder excess) runs in O(n) time and O(h) extra space. Each node is visited once.
Which pattern does Distribute Coins in Binary Tree use?
It is a trees & bst problem that uses the postorder + multiple return values pattern. Other problems with the same pattern: Balanced Binary Tree, Validate Binary Search Tree, Children Sum in a Binary Tree.
Is there a brute force solution for Distribute Coins in Binary Tree?
Yes. Brute force (count each edge separately) takes O(n²) time and O(h) space. Every edge from a node to its parent is crossed exactly |coins in subtree - nodes in subtree| times.
Which edge cases should I test for Distribute Coins in Binary Tree?
Every node already holds one coin: 0 moves; All coins sit on one leaf and must travel across the whole tree; A single node with one coin; Coins must pass through a node that itself has zero coins.