Distribute Coins in Binary Tree

In a binary tree with n nodes, each node has some number of coins, and there are a total of n coins throughout the entire tree. The goal is to distribute the coins in such a way that every node has exactly one coin, using the minimum number of moves. A move consists of transferring a coin between adjacent (parent-child) nodes.

Solution

To solve this problem, we’ll use a Depth-First Search (DFS) algorithm to traverse the tree. At each node, we’ll determine the surplus or deficit of coins and move them accordingly.

Python solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def distributeCoins(self, root: Optional[TreeNode]) -> int:
        self.moves = 0

        def dfs(node):
            if not node:
                return 0
            left = dfs(node.left)
            right = dfs(node.right)
            self.moves += abs(left) + abs(right)
            return node.val + left + right - 1

        dfs(root)
        return self.moves

Explanation

• dfs(node) is a recursive function that calculates the number of surplus or deficit coins for the current node.
• left and right variables store the surplus or deficit from the left and right children, respectively.
• The number of moves required to balance the current node is the absolute sum of the left and right values. We increment the self.moves variable by this amount.
• Finally, we return the surplus or deficit for the current node, which will be the node’s value plus the left and right surplus/deficit minus 1 (as the current node needs exactly one coin).

The final result will be stored in self.moves, which represents the minimum number of moves required to distribute the coins such that every node has exactly one coin.