hardTreesPure DSA~30 min
Minimum Moves to Balance Tokens Across a Tree
Each node of a binary tree holds some tokens; the total token count equals the number of nodes. In one move a token shifts along one edge. Find the minimum moves so every node holds exactly one token.
Problem
Given the root of a binary tree with n nodes where node values are token counts summing to n, in each move you may move one token from a node to an adjacent node. Return the minimum number of moves to make every node hold exactly one token.
Input
The root of a binary tree (given as a level-order array in examples).
Output
An integer: the minimum number of moves.
Constraints
- 1 <= n <= 100
- 0 <= Node.val <= n; the sum of all values equals n.
Examples
Example 1
Input
root = [3,0,0]
Output
2
Move one token from the root to each child: 2 moves.
Example 2
Input
root = [0,3,0]
Output
3
Three tokens travel from the left child outward: 3 moves.