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 another. 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.
Example 1:
Input: root = [3,0,0] Output: 2 Explanation: From the root of the tree, we move one coin to its left child, and one coin to its right child.
Example 2:
Input: root = [0,3,0] Output: 3 Explanation: From the left child of the root, we move two coins to the root [taking two moves]. Then, we move one coin from the root of the tree to the right child.
Constraints:
n.1 <= n <= 1000 <= Node.val <= nNode.val is n.The key idea in #979 Distribute Coins in Binary Tree is to balance coins across all nodes so that each node ends up with exactly one coin. Since coins can only move between adjacent nodes (parent and child), the problem naturally fits a Depth-First Search (DFS) traversal.
During a postorder DFS, process the left and right subtrees before the current node. Each subtree returns the number of excess or missing coins it contributes to its parent. A positive value means extra coins can be passed upward, while a negative value means coins are needed from the parent.
At each node, the number of moves required is determined by the absolute value of the balances coming from its children. Accumulate these moves globally while propagating the net balance upward.
This strategy works efficiently because every node is visited exactly once. The algorithm runs in O(n) time with O(h) space complexity due to the recursion stack, where n is the number of nodes and h is the tree height.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| DFS Postorder Traversal | O(n) | O(h) |
Nick White
To solve the problem, we perform a post-order traversal of the tree. During this traversal, for each node, we calculate the excess coins (i.e., the number of coins - 1) that need to be moved either up to the parent or down to the children. We accumulate the absolute values of excess coins for each move.
Time Complexity: O(n), where n is the number of nodes in the tree. We visit each node exactly once.
Space Complexity: O(h), where h is the height of the tree due to the recursion stack.
1class TreeNode:
2 def __init__(self, val=0, left=None, right=None):
3 self.val = val
4 self.left = left
5 self.right = right
6
7class Solution:
8 def distributeCoins(self, root: TreeNode) -> int:
9 self.moves = 0
10
11 def dfs(node):
12 if not node:
13 return 0
14 left_excess = dfs(node.left)
15 right_excess = dfs(node.right)
16 self.moves += abs(left_excess) + abs(right_excess)
17 return node.val + left_excess + right_excess - 1
18
19 dfs(root)
20 return self.movesThis code defines a binary tree node with a value and optional left and right children. The distributeCoins function calculates the minimum number of moves needed to distribute coins such that each node has exactly one coin. The dfs helper function calculates the excess coins at each node using post-order traversal and updates the global count of moves.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of this problem appear in technical interviews at major tech companies. It tests understanding of tree traversal, DFS recursion, and how to propagate information from child nodes to parent nodes.
A binary tree structure combined with recursion is the most suitable. DFS traversal allows you to process child nodes first and propagate coin balances upward efficiently.
The optimal approach uses a postorder Depth-First Search (DFS). Each subtree calculates how many extra or missing coins it has and passes this balance to its parent while counting the required moves.
Postorder traversal ensures that both left and right subtrees are processed before evaluating the current node. This allows the algorithm to correctly compute coin balances from children and determine the number of moves needed.