Move coins between adjacent tree nodes so every node ends with exactly one coin, using the minimum total moves.
You are given the root of a binary tree where each node contains some number of coins. In one move, you may transfer a single coin between a node and one of its directly connected neighbors (its parent or one of its children).
Your task is to determine the minimum number of moves required so that every node in the tree ends with exactly one coin.
A coin can only be moved across one edge at a time, and the total number of coins in the tree is guaranteed to match the number of nodes, so a solution always exists.
Input Format
- A binary tree root is provided in the usual node format.
- Each node has an integer value representing the number of coins at that node.
Output Format
- Return a single integer: the minimum number of moves needed so every node has exactly one coin.
Constraints
- The tree has at least 1 node.
- Node values are non-negative integers.
- The total number of coins equals the number of nodes.
- A move transfers exactly 1 coin across exactly 1 edge.
Example 1
Input
root = [3,0,0]
Output
2
Explanation
The root has 3 coins and each child has 0. Move 1 coin from the root to the left child and 1 coin from the root to the right child, for a total of 2 moves.
Example 2
Input
root = [0,3,0]
Output
3
Explanation
The middle node has 3 coins. It sends 1 coin to itself? No—coins can only move along edges. One valid sequence is to move one coin from the middle node to the root, then from the root to the left child, and move the remaining coin from the middle node to the right child. The minimum total is 3 moves.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.