979. Distribute Coins in Binary Tree - Explanation

Problem Link

1. Depth First Search

Intuition

Each node needs exactly one coin. If a subtree has more coins than nodes, the excess must flow up to the parent. If it has fewer coins than nodes, the deficit must be supplied from the parent. The number of moves across each edge equals the absolute difference between the subtree size and its total coins. By computing size and coins for each subtree during a post-order traversal, we can sum up all the required moves.

Algorithm

1. Initialize a global counter res to 0.
2. Define a recursive dfs function that returns [size, coins] for each subtree.
3. For a null node, return [0, 0].
4. Recursively compute [l_size, l_coins] and [r_size, r_coins] for left and right children.
5. Calculate size = 1 + l_size + r_size and coins = cur.val + l_coins + r_coins.
6. Add abs(size - coins) to res (moves needed across the edge to the parent).
7. Return [size, coins].
8. Call dfs on the root and return res.

# Definition for a binary tree node.
# 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: Optional[TreeNode]) -> int:
        self.res = 0

        def dfs(cur):
            if not cur:
                return [0, 0]  # [size, coins]

            l_size, l_coins = dfs(cur.left)
            r_size, r_coins = dfs(cur.right)

            size = 1 + l_size + r_size
            coins = cur.val + l_coins + r_coins
            self.res += abs(size - coins)

            return [size, coins]

        dfs(root)
        return self.res

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$ for recursion stack.

---

2. Depth First Search (Optimal)

Intuition

We can simplify the previous approach by tracking only the "extra coins" at each node. A node with val coins has val - 1 extra coins (positive means surplus, negative means deficit). Each node's extra coins include its own plus what flows up from its children. The absolute value of extra coins at each node represents exactly how many coins must cross the edge to its parent.

Algorithm

1. Initialize a global counter res to 0.
2. Define a recursive dfs function that returns the extra coins for each subtree.
3. For a null node, return 0.
4. Recursively get l_extra and r_extra from left and right children.
5. Calculate extra_coins = cur.val - 1 + l_extra + r_extra.
6. Add abs(extra_coins) to res.
7. Return extra_coins.
8. Call dfs on the root and return res.

# Definition for a binary tree node.
# 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: Optional[TreeNode]) -> int:
        self.res = 0

        def dfs(cur):
            if not cur:
                return 0  # extra_coins

            l_extra = dfs(cur.left)
            r_extra = dfs(cur.right)

            extra_coins = cur.val - 1 + l_extra + r_extra
            self.res += abs(extra_coins)
            return extra_coins

        dfs(root)
        return self.res

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$ fo recursion stack.

---

3. Breadth First Search

Intuition

We can avoid recursion by using BFS to collect nodes level by level, then processing them in reverse order (leaves first). For each node, we transfer its extra coins (val - 1) to its parent and count the moves. Processing in reverse BFS order ensures children are handled before their parents, mimicking the post-order behavior of DFS.

Algorithm

1. Use a queue to perform BFS starting from the root.
2. Store each node in a list and build a parent_map during traversal.
3. After BFS completes, process nodes in reverse order.
4. For each node (except the root), transfer node.val - 1 to its parent and add abs(node.val - 1) to the result.
5. Return the total move count.

# Definition for a binary tree node.
# 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: Optional[TreeNode]) -> int:
        res = 0
        q = deque([root])
        parent_map = {}

        nodes = []
        while q:
            node = q.popleft()
            nodes.append(node)
            if node.left:
                parent_map[node.left] = node
                q.append(node.left)
            if node.right:
                parent_map[node.right] = node
                q.append(node.right)

        while nodes:
            node = nodes.pop()
            if node in parent_map:
                parent = parent_map[node]
                parent.val += node.val - 1
                res += abs(node.val - 1)

        return res

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$

---

4. Iterative DFS

Intuition

This approach simulates recursive DFS using an explicit stack. We use a visit set to distinguish between the first visit (when we push children) and the second visit (when we process the node after its children are done). On the second visit, we accumulate coins from children, compute the extra coins, and add the absolute value to our result.

Algorithm

1. Initialize a stack with the root and an empty visit set.
2. While the stack is not empty:
   • Pop a node. If not visited, push it back, mark as visited, then push its children.
   • If already visited, add the children's values to the current node, subtract 1, and add abs(node.val) to the result.
3. Return the total move count.

# Definition for a binary tree node.
# 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: Optional[TreeNode]) -> int:
        stack = [root]
        res = 0
        visit = set()

        while stack:
            node = stack.pop()

            if node not in visit:
                stack.append(node)
                visit.add(node)

                if node.right:
                    stack.append(node.right)
                if node.left:
                    stack.append(node.left)
            else:
                if node.left:
                    node.val += node.left.val
                if node.right:
                    node.val += node.right.val

                node.val -= 1
                res += abs(node.val)
                visit.remove(node)

        return res

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$

---

Common Pitfalls

Forgetting to Take Absolute Value

The extra coins at a node can be positive (surplus) or negative (deficit). Both represent moves across the edge to the parent. Forgetting to take the absolute value counts deficits as negative moves, producing wrong results.

# Wrong: Not taking absolute value
extra_coins = cur.val - 1 + l_extra + r_extra
self.res += extra_coins  # Negative values reduce count!

# Correct: Take absolute value
extra_coins = cur.val - 1 + l_extra + r_extra
self.res += abs(extra_coins)

Counting Moves at the Wrong Time

In the DFS approach, moves should be counted after processing both children. Counting moves before the recursive calls or only for one child leads to incorrect totals.

# Wrong: Counting before children are processed
def dfs(cur):
    self.res += abs(cur.val - 1)  # Children not accounted for!
    dfs(cur.left)
    dfs(cur.right)

# Correct: Count after combining with children's results
def dfs(cur):
    l_extra = dfs(cur.left)
    r_extra = dfs(cur.right)
    extra_coins = cur.val - 1 + l_extra + r_extra
    self.res += abs(extra_coins)
    return extra_coins

Returning Wrong Value from DFS

The DFS function must return the net extra coins (surplus or deficit) that flow to the parent, not the move count. Returning the wrong value breaks the recursive accumulation.

# Wrong: Returning the move count
def dfs(cur):
    moves = abs(cur.val - 1)
    return moves  # Parent needs extra coins, not moves!

# Correct: Return net extra coins for parent
def dfs(cur):
    l_extra = dfs(cur.left) if cur.left else 0
    r_extra = dfs(cur.right) if cur.right else 0
    extra_coins = cur.val - 1 + l_extra + r_extra
    self.res += abs(extra_coins)
    return extra_coins  # Net flow to parent