We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Distribute Coins in Binary Tree

Difficulty: Medium

Problem Description

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.

Key Insights

  • Each node should end up with exactly one coin.
  • The total number of coins in the tree equals the number of nodes (n), ensuring that redistribution is feasible.
  • A depth-first search (DFS) approach can be used to traverse the tree and calculate the number of moves needed.
  • The difference between the coins at each node and the required one coin can be propagated up and down the tree.

Space and Time Complexity

Time Complexity: O(n) - We visit each node exactly once. Space Complexity: O(h) - The space used by the recursion stack, where h is the height of the tree.

Solution

We will use a depth-first search (DFS) to traverse the binary tree. As we visit each node, we will calculate the excess or deficit of coins at that node. The excess (or deficit) will be propagated to the parent node, and the number of moves needed will be accumulated as we traverse. This approach effectively balances the number of coins across the tree while counting the required moves.

Code Solutions

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def distributeCoins(self, root: TreeNode) -> int:
        self.moves = 0
        
        def dfs(node):
            if not node:
                return 0
            
            left_excess = dfs(node.left)   # Coins excess from left subtree
            right_excess = dfs(node.right) # Coins excess from right subtree
            
            # Update moves with the absolute excess from left and right children
            self.moves += abs(left_excess) + abs(right_excess)
            
            # Return the excess coins to parent: node.val - 1 (needs 1 coin)
            return node.val - 1 + left_excess + right_excess
        
        dfs(root)
        return self.moves
← Back to All Questions