{x}
blog image

Distribute Coins in Binary Tree

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.

 

Example 1:

Input: root = [3,0,0]
Output: 2
Explanation: From the root of the tree, we move one coin to its left child, and one coin to its right child.

Example 2:

Input: root = [0,3,0]
Output: 3
Explanation: From the left child of the root, we move two coins to the root [taking two moves]. Then, we move one coin from the root of the tree to the right child.

 

Constraints:

  • The number of nodes in the tree is n.
  • 1 <= n <= 100
  • 0 <= Node.val <= n
  • The sum of all Node.val is n.

979. Distribute Coins in Binary Tree

Problem Description

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. The goal is to find the minimum number of moves required to make every node have exactly one coin.

Solution: Depth-First Search (DFS)

This problem can be efficiently solved using a Depth-First Search (DFS) approach. The core idea is to track the surplus or deficit of coins in each subtree.

Algorithm:

  1. DFS Function (dfs): A recursive function that processes each node.
  2. Base Case: If the current node is null, return 0 (no coins).
  3. Recursive Calls: Recursively call dfs on the left and right children to get the coin surplus/deficit in their subtrees (left and right).
  4. Move Calculation: The absolute values of left and right represent the number of moves needed to balance the coins within the subtree rooted at the current node. Add abs(left) + abs(right) to the total moves count (ans).
  5. Surplus/Deficit Calculation: Calculate the net surplus/deficit of coins in the current subtree: left + right + root.val - 1. This represents the number of coins that need to be moved up or down from this subtree to its parent.
  6. Return Value: Return the calculated surplus/deficit for the current subtree.

Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node exactly once.

Space Complexity: O(H), where H is the height of the tree. This is due to the recursive call stack used in the DFS. In the worst case (a skewed tree), H can be N.

Code Implementation

Here's the code implementation in several popular programming languages:

Python3:

# 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:
        ans = 0
 
        def dfs(node):
            nonlocal ans
            if not node:
                return 0
            left = dfs(node.left)
            right = dfs(node.right)
            ans += abs(left) + abs(right)
            return left + right + node.val - 1
 
        dfs(root)
        return ans

Java:

class Solution {
    int ans = 0;
 
    public int distributeCoins(TreeNode root) {
        dfs(root);
        return ans;
    }
 
    private int dfs(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int left = dfs(node.left);
        int right = dfs(node.right);
        ans += Math.abs(left) + Math.abs(right);
        return left + right + node.val - 1;
    }
}

C++:

class Solution {
public:
    int ans = 0;
    int distributeCoins(TreeNode* root) {
        dfs(root);
        return ans;
    }
 
    int dfs(TreeNode* node) {
        if (!node) return 0;
        int left = dfs(node->left);
        int right = dfs(node->right);
        ans += abs(left) + abs(right);
        return left + right + node->val - 1;
    }
};

Go:

func distributeCoins(root *TreeNode) int {
    ans := 0
    var dfs func(*TreeNode) int
    dfs = func(node *TreeNode) int {
        if node == nil {
            return 0
        }
        left := dfs(node.Left)
        right := dfs(node.Right)
        ans += abs(left) + abs(right)
        return left + right + node.Val - 1
    }
    dfs(root)
    return ans
}
 
func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

TypeScript:

function distributeCoins(root: TreeNode | null): number {
    let ans = 0;
    const dfs = (node: TreeNode | null): number => {
        if (!node) return 0;
        const left = dfs(node.left);
        const right = dfs(node.right);
        ans += Math.abs(left) + Math.abs(right);
        return left + right + node.val - 1;
    };
    dfs(root);
    return ans;
};

These code examples all follow the same algorithmic approach, demonstrating its elegance and efficiency in solving this problem. Remember that you'll need a TreeNode definition appropriate for your chosen language.