Coin Balancing Moves

MediumTrees

Problem

A binary tree has n nodes and exactly n coins in total; node.val is how many coins sit on that node. In one move you may pass a single coin along one edge, between a parent and a child, in either direction.

Return the minimum number of moves so that every node ends up with exactly one coin.

Example 1

Input:
root = [3, 0, 0]
Output:
2

The root sends one coin to each child.

Example 2

Input:
root = [0, 3, 0]
Output:
3

The left child sends one coin up to the root (1 move) and one coin up and down to the right child (2 moves).

Constraints

  • 1 ≤ n ≤ 10^4
  • Tree height ≤ 500
  • 0 ≤ node.val ≤ n
  • The values sum to n.

Hint

Show the first hint

Focus on one edge, between a node and its parent. How many coins must cross it, at minimum?

Walkthrough

How to approach it

01Clarify before coding

  • Can a coin travel several edges? Yes, each edge crossed is one move.
  • Is the total always n? Yes, so a solution always exists.
  • Can a node temporarily hold zero or many coins? Yes, only the final state matters.

02Brute force

Treat it as a matching between surplus coins and empty nodes and minimise total distance, e.g. via min-cost flow.

Cost: Polynomial but heavy (min-cost flow on n nodes), and much harder to code than needed.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.