Coding · Trees
Distribute Coins in Binary Tree
- Reported once
- Medium
- SDE-2
- 1 source
One candidate write-up. Treat it as a single data point.
Solve it in the playground, with tests
A binary tree has N nodes and holds exactly N coins in total, spread over the nodes (some may hold none). In one move you pass one coin between two nodes joined by an edge. Return the minimum number of moves so every node holds exactly one coin. The tree is a level-order array with null for missing children, and [0,3,0] needs 3 moves; there are up to 100 nodes.
Restated in our own words, not a quote from PhonePe or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
I would ask: is the total number of coins guaranteed to equal the number of nodes, or must I detect the impossible case? Is a move one coin across one edge, so carrying a coin through an intermediate node costs one move per edge? Are coin counts non-negative integers? How is the tree encoded, and what do I return for an empty tree?
I would assume the totals match, a move is one coin over one edge, and the array uses the usual level-order format where the children of a missing node are not listed. An empty array or a null root returns 0.
Brute force
Say the obvious answer and why it is too slow.
Treat the whole configuration as a state: the number of coins on each node. A move changes one state into a neighbor, so run a breadth-first search from the starting state to the all-ones state; the depth you reach it at is the answer.
It is correct but the state space is the number of ways to spread N coins over N nodes, which is the binomial coefficient C(2N-1, N). For N = 10 that is already 92,378 states, and for N = 100 it is a number with about 59 digits. Any search over configurations collapses long before the stated size, and a greedy rule about which coin to move first is easy to get wrong.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(N · C(2N-1, N))
- Time
- O(N)
- Space
- O(N) with the tree built
Stop thinking about individual coins and look at one edge at a time. Cut the edge between a node and its parent. The subtree below has some number of nodes S and holds some number of coins C. At the end it must hold exactly S coins, so a net C - S coins must cross that edge: upward if positive, downward if negative. Every coin crossing costs one move on that edge, so at least |C - S| moves are unavoidable there. Summing over all edges gives a lower bound.
That bound is achievable. Orient each edge in the direction its coins must flow; a tree has no cycles, so some node has all its incoming flow finished and still has outgoing flow. That node holds one coin plus everything it still has to send, so it can send. Repeat, and no move is ever wasted or impossible.
This is a post-order tree traversal that returns a value to the parent. For each node compute its excess: the node's coins plus the excess of the left child plus that of the right child, minus one for the node itself. That equals coins minus nodes in the subtree. Before returning, add |left excess| + |right excess| to a running move total, because those are the coins crossing the two child edges. A missing child contributes 0.
Out loud: each node tells its parent how many coins it has to spare or needs, and the parent pays one move per coin on each child edge.
Walk it through
A dry run on the example, step by step.
| Node | Coins | Child excess (L, R) | Returns | Moves so far |
|---|---|---|---|---|
| leaf 3 | 3 | 0, 0 | 2 | 0 |
| left 0 | 0 | 0, 2 | 1 | 2 |
| right 0 | 0 | 0, 0 | -1 | 2 |
| root 1 | 1 | 1, -1 | 0 | 4 |
Take the level-order array [1,0,0,null,3]. The root holds 1 coin and has two children holding 0 each; the left child has a single child on its right with 3 coins. The post-order visit order is: leaf with 3, left 0, right 0, root.
The leaf has excess 3 + 0 + 0 - 1 = 2 and adds no moves. The left 0 node sees a child excess of 2, so it adds 2 moves, and its own excess is 0 + 2 - 1 = 1. The right 0 node has no children and returns -1. The root sees excesses 1 and -1, adds 1 + 1 = 2 moves, and returns 1 + 1 - 1 - 1 = 0, a balanced tree. The total is 4, and the table lists the steps.
The code
Runnable JavaScript, checked against test cases.
function buildTree(values) {
if (values.length === 0 || values[0] === null) return null;
const root = { val: values[0], left: null, right: null };
const queue = [root];
let head = 0;
let i = 1;
while (head < queue.length && i < values.length) {
const node = queue[head++];
if (i < values.length && values[i] !== null) {
node.left = { val: values[i], left: null, right: null };
queue.push(node.left);
}
i++;
if (i < values.length && values[i] !== null) {
node.right = { val: values[i], left: null, right: null };
queue.push(node.right);
}
i++;
}
return root;
}
function distributeCoins(levelOrder) {
const root = buildTree(levelOrder);
let moves = 0;
function excess(node) {
if (node === null) return 0;
const fromLeft = excess(node.left);
const fromRight = excess(node.right);
moves += Math.abs(fromLeft) + Math.abs(fromRight);
return node.val + fromLeft + fromRight - 1;
}
excess(root);
return moves;
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
A single node (which must hold exactly one coin) has nothing to move and returns 0. A tree where every node already holds one coin has all excesses 0, so the answer is 0. An empty array, or a null root, returns 0 through the guard at the top.
Negative excesses (a subtree that needs coins) are counted with the absolute value, so coins moving down cost the same as coins moving up. A path with all coins at the deepest node pays the sum of the distances, which the per-edge counting produces automatically.
The level-order builder reads children from a queue, not from heap positions, because the encoding skips the children of missing nodes. The recursion depth equals the tree height, at most 100 here.
Follow-ups to expect
Where the interviewer pushes next.
- What would you return, and how would you detect it, if the coins did not add up to the number of nodes?
- How would you output the actual sequence of moves rather than just their count?
- If every edge had a different cost per coin, what changes in the formula?
- How would the problem change on a general graph with cycles instead of a tree?
- How would you avoid deep recursion if the tree could be 100,000 nodes deep?
Where candidates slip
The mistakes this problem punishes.
Forgetting the absolute value, so a deficit cancels a surplus and the answer comes out too small. Forgetting the minus one for the node's own coin, which makes every excess too large.
Other slips: returning the move count from the recursion instead of the excess, so the parent computes nonsense; simulating the coins one by one with a greedy rule; and building the tree with heap indexing (children of i at 2i + 1 and 2i + 2). That is wrong here, because this encoding omits the children of missing nodes. Also watch that moves is shared across calls: it must be one running total, not reset in each call.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.