Distribute Coins in Binary Tree

Problem A binary tree of n nodes holds n coins total (some nodes 0, some several). One move transfers one coin between adjacent (parent–child) nodes. Return the minimum moves so every node ends with exactly one coin.

Input / Output

• Input: tree root. Output: min move count.

Constraints

• n up to 100 classically; O(n) post-order expected.

Example

• [3,0,0] → 2 (root sends one coin to each child); [0,3,0] → 3 (left child pushes 2 up, root pushes 1 right → 2+1).

Expected approach

• Post-order returning each subtree's NET flow: excess(node) = coins + excess(left) + excess(right) − 1 (negative = deficit pulled from parent). Every coin crossing an edge is one move, in either direction, so moves += |excess(left)| + |excess(right)| accumulated globally. O(n)/O(h). The |flow-per-edge| insight — counting edge traffic rather than simulating movement — is the entire question; walk the [0,3,0] example to demonstrate it.