Problem Description

You have a binary tree with n nodes, where each node contains some number of coins (stored in node.val). The total number of coins across all nodes equals n, meaning there are exactly n coins distributed throughout the tree.

Your goal is to redistribute these coins so that every node has exactly one coin. You can move coins between adjacent nodes (parent to child or child to parent), with each coin movement counting as one "move."

The task is to find the minimum number of moves required to achieve this distribution where each node has exactly one coin.

For example, if a node has 3 coins, it needs to give away 2 coins to its neighbors. If a node has 0 coins, it needs to receive 1 coin from a neighbor. The challenge is to calculate the total minimum moves needed across the entire tree to balance all nodes to have exactly 1 coin each.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: A binary tree is a special type of graph with nodes (tree nodes) and edges (parent-child relationships).

Is it a tree?

• Yes: The problem explicitly states we're working with a binary tree where we need to redistribute coins among nodes.

DFS

• We arrive at DFS: Since we're dealing with a tree structure and need to process information from children nodes to parent nodes (calculating coin surplus/deficit from leaves up to root), DFS is the appropriate approach.

Conclusion: The flowchart suggests using a DFS (Depth-First Search) approach for this problem. This makes sense because:

1. We need to traverse the entire tree to understand coin distribution
2. We need to calculate information bottom-up (from leaves to root) to determine how many coins need to move through each edge
3. Each subtree's coin balance affects its parent's calculation, making post-order DFS traversal ideal for accumulating the minimum moves required

Intuition

The key insight is to think about what happens at each subtree. For any node in the tree, we need to ensure that the subtree rooted at that node has exactly the right number of coins for its nodes. If a subtree has 5 nodes, it needs exactly 5 coins total.

Consider what happens when a subtree has excess or deficit coins:

• If a subtree has more coins than nodes (e.g., 7 coins for 5 nodes), the extra 2 coins must flow out through the parent edge
• If a subtree has fewer coins than nodes (e.g., 3 coins for 5 nodes), it needs 2 coins to flow in through the parent edge

The crucial observation is that every coin that needs to move from one subtree to another must pass through the edge connecting that subtree to its parent. Whether we have excess coins to send up or need coins to flow down, the absolute value of this difference represents the number of moves through that edge.

For each node, we can calculate its "balance" as: left_balance + right_balance + node.val - 1

• left_balance: excess/deficit from left subtree
• right_balance: excess/deficit from right subtree
• node.val - 1: the current node's excess/deficit (it has node.val coins but needs exactly 1)

The number of moves required at this node is |left_balance| + |right_balance| because:

• If left subtree has +3 balance, 3 coins move from left child to current node
• If right subtree has -2 balance, 2 coins move from current node to right child
• Both movements count toward our total moves

By recursively calculating this from the leaves up to the root, we accumulate the total minimum moves needed to balance the entire tree.

Learn more about Tree, Depth-First Search and Binary Tree patterns.

Solution Approach

The solution implements a DFS traversal that calculates the coin overload for each subtree. The coin overload represents how many extra coins a subtree has (positive) or how many it needs (negative).

We define a recursive function dfs(root) that processes each node in post-order traversal:

1. Base Case: If the node is None, return 0 (no coin overload for empty subtrees).

2. Recursive Calls: First, recursively calculate the coin overload for left and right subtrees:

   • left = dfs(root.left): Get the coin overload from the left subtree
   • right = dfs(root.right): Get the coin overload from the right subtree

3. Count Moves: The number of moves through the current node equals abs(left) + abs(right):

   • abs(left): Number of coins that must flow between current node and left child
   • abs(right): Number of coins that must flow between current node and right child
   • Add this to our global answer counter ans

4. Calculate Current Subtree's Overload: Return the total overload for the subtree rooted at current node:

   • Formula: left + right + root.val - 1
   • left + right: Net coins from children
   • root.val: Coins at current node
   • -1: One coin that must remain at current node
   • This value tells the parent how many coins this entire subtree has in excess or deficit

The algorithm uses a nonlocal variable ans to accumulate the total moves across all nodes. After the DFS completes, ans contains the minimum number of moves required to distribute exactly one coin to each node.

The time complexity is O(n) as we visit each node once, and the space complexity is O(h) where h is the height of the tree due to the recursion stack.

Example Walkthrough

Let's walk through a concrete example to illustrate how the solution works.

Consider this binary tree:

       0
      / \
     3   0

We have 3 nodes total and 3 coins total (all at the left child). Our goal is to redistribute so each node has exactly 1 coin.

Step 1: Process the left child (leaf node with value 3)

• This is a leaf node, so left = 0 and right = 0 (no children)
• Calculate moves at this node: |0| + |0| = 0
• Calculate overload for this subtree: 0 + 0 + 3 - 1 = 2
• This node has 2 extra coins that need to flow up to its parent
• Running total moves: 0

Step 2: Process the right child (leaf node with value 0)

• This is a leaf node, so left = 0 and right = 0
• Calculate moves at this node: |0| + |0| = 0
• Calculate overload for this subtree: 0 + 0 + 0 - 1 = -1
• This node needs 1 coin from its parent
• Running total moves: 0

Step 3: Process the root node (value 0)

• We've already processed its children:
  • Left child returns overload of +2 (has 2 extra coins)
  • Right child returns overload of -1 (needs 1 coin)
• Calculate moves at this node: |2| + |-1| = 2 + 1 = 3
  • 2 coins must move from left child to root
  • 1 coin must move from root to right child
• Running total moves: 0 + 3 = 3
• Calculate overload for entire tree: 2 + (-1) + 0 - 1 = 0
  • This should always be 0 for the root since total coins equals total nodes

Final Distribution: After 3 moves, the tree becomes:

       1
      / \
     1   1

The moves were:

1. Move 1 coin from left child to root
2. Move another coin from left child to root
3. Move 1 coin from root to right child

This matches our calculated answer of 3 minimum moves.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm performs a depth-first search (DFS) traversal of the binary tree. Each node is visited exactly once during the traversal. At each node, the algorithm performs constant time operations:

• Checking if the node is None
• Calculating the excess/deficit of coins (left + right + root.val - 1)
• Updating the answer with abs(left) + abs(right)

Since we visit all n nodes exactly once and perform O(1) operations at each node, the overall time complexity is O(n).

Space Complexity: O(h)

The space complexity is determined by the recursive call stack used during the DFS traversal. In the worst case, the recursion depth equals the height of the binary tree:

• For a balanced binary tree, the height h = O(log n), resulting in O(log n) space complexity
• For a skewed binary tree (essentially a linked list), the height h = O(n), resulting in O(n) space complexity

Therefore, the space complexity is O(h) where h is the height of the binary tree. No additional data structures are used that scale with the input size; only the ans variable uses O(1) extra space.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding the Balance Calculation

A common mistake is incorrectly calculating what each subtree should return. Developers often confuse:

• The number of moves (which we accumulate in total_moves)
• The coin balance/overload (which we return from the function)

Incorrect approach:

def calculate_balance(node):
    if node is None:
        return 0
  
    left_balance = calculate_balance(node.left)
    right_balance = calculate_balance(node.right)
  
    # WRONG: Returning moves instead of balance
    return abs(left_balance) + abs(right_balance)

Correct approach: The function should return the net coin surplus/deficit for the subtree, not the number of moves.

2. Forgetting to Use Absolute Values for Move Counting

When counting moves, both positive (excess) and negative (deficit) balances represent coins that must move. Forgetting to use absolute values leads to incorrect move counts.

Incorrect:

# WRONG: Not using absolute values
total_moves += left_balance + right_balance

Correct:

# RIGHT: Both excess and deficit require moves
total_moves += abs(left_balance) + abs(right_balance)

3. Off-by-One Error in Balance Formula

The formula left + right + root.val - 1 is crucial. Common mistakes include:

• Forgetting the -1 (which accounts for keeping one coin at the current node)
• Using +1 instead of -1

Incorrect:

# WRONG: Forgot to subtract 1
return left_balance + right_balance + node.val

# WRONG: Added 1 instead of subtracting
return left_balance + right_balance + node.val + 1

Correct:

# RIGHT: Subtract 1 for the coin that stays at current node
return left_balance + right_balance + node.val - 1

4. Using Global Variables Instead of Nonlocal

In Python, when modifying a variable from an outer scope inside a nested function, you must declare it as nonlocal. Using global or forgetting the declaration entirely causes errors.

Incorrect:

def distributeCoins(self, root):
    total_moves = 0
  
    def calculate_balance(node):
        # WRONG: Missing nonlocal declaration
        total_moves += abs(left_balance) + abs(right_balance)
        # This will raise UnboundLocalError

Correct:

def distributeCoins(self, root):
    total_moves = 0
  
    def calculate_balance(node):
        nonlocal total_moves  # Correct declaration
        total_moves += abs(left_balance) + abs(right_balance)

5. Not Handling Edge Cases

While the problem guarantees n nodes with n coins total, implementations should still handle:

• Single node trees (where no moves are needed)
• Skewed trees (all nodes in a line)

These cases work correctly with the standard algorithm but can trip up alternative approaches that make assumptions about tree structure.