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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Distribute Coins in Binary Tree

Number: 1021

Difficulty: Medium

Paid? No

Companies: Google, Amazon, Meta, Microsoft, PhonePe

Problem Description

Given the root of a binary tree where each node holds a certain number of coins and the total number of coins equals the number of nodes, the goal is to perform moves (each move transfers one coin between adjacent nodes) such that every node ends up with exactly one coin. Determine the minimum number of moves required.

Key Insights

  • Each node’s balance is defined as (number of coins at the node) - 1, which indicates the surplus (if positive) or deficit (if negative).
  • Use a Depth-First Search (DFS) traversal (post-order) to process children before handling the parent.
  • At each node, the number of moves required is the sum of the absolute balances from its left and right subtrees.
  • The DFS returns the net balance for each subtree so that these balances can be accumulated at the parent.
  • The total moves required is the sum of the absolute values of the surplus/deficits transferred across each edge.

Space and Time Complexity

Time Complexity: O(n) since each node is processed once. Space Complexity: O(h), where h is the height of the tree (due to recursion stack).

Solution

We solve the problem by performing a post-order DFS traversal on the tree. At every node, compute the net coin balance (node.val + left balance + right balance - 1). The moves needed at that node are the absolute values of the left and right balances, reflecting the coins that must be moved into or out of that subtree. Accumulate these moves during the traversal. Finally, the sum of all moves gives the minimum number of moves required to achieve the desired coin distribution.

Code Solutions

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val  # number of coins at the node
        self.left = left  # left child
        self.right = right  # right child

class Solution:
    def distributeCoins(self, root: TreeNode) -> int:
        self.moves = 0  # initialize the move counter
        
        def dfs(node):
            if not node:
                return 0  # base case: null nodes contribute 0 balance
            # Recursively process left and right children
            left_balance = dfs(node.left)
            right_balance = dfs(node.right)
            # Accumulate moves: absolute coin imbalances from both children
            self.moves += abs(left_balance) + abs(right_balance)
            # Return the current node's net balance
            return node.val + left_balance + right_balance - 1
        
        dfs(root)
        return self.moves
← Back to All Questions