DSA problem
Distribute Coins in Binary Tree
You are given the root of a binary tree with n nodes where each node in the tree has node.val coins. There are n coins in total throughout the whole tree. In one move, we may choose two adjacent nodes and move one coin from one node to the other (a move may be from parent to child or from child to parent). Return the minimum number of moves required to make every node have exactly one coin.
The key insight is to look at any edge in the tree. After all moves are done, each subtree contains exactly as many coins as it has nodes — anything else would mean some node ends up with a wrong count. Therefore the net flow across the edge connecting any subtree to its parent equals coins_in_subtree − nodes_in_subtree. Whether that quantity is positive (excess flows up) or negative (deficit flows down), the absolute value counts as one move per coin per edge.
This naturally maps onto a post-order recursion: at each node, compute the excess (or deficit) of its subtree by combining the values returned from its two children. The total work each subtree contributes to the answer is the absolute value of the left child's excess plus the absolute value of the right child's excess; we accumulate these into a global counter as the recursion unwinds. The value we return to our parent is node.val + leftExcess + rightExcess − 1 — the running excess for our subtree, after we have kept one coin for ourselves.
The algorithm visits each node once and performs constant work, so it runs in O(n) time and uses O(h) call-stack space.
Examples
root = [3,0,0]2root = [0,3,0]3root = [1,0,2]2Constraints
- The number of nodes in the tree is n.
- 1 <= n <= 100
- 0 <= Node.val <= n
- The sum of all Node.val equals n.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.