Leetcode 979. Distribute Coins in Binary Tree

Problem Explanation

Given a binary tree where each node has a certain number of coins, the object is to distribute the coins such that every node has exactly one coin. We can move coins from one node to another, but the nodes need to be adjacent (i.e., parent-child). We need to find the minimum number of moves to achieve this.

Let’s take an example from problem statement itself, [3,0,0] it's a binary tree represented as an array, 3 is the root node and 0's are its left and right childs.

1
2
3  3
4 / \
50   0

To distribute the coins equally to each node, we have to move 1 coin to the left node and 1 coin to the right node. Which means we need 2 moves.

Solution Explanation

This is a depth-first search (DFS) problem. For each subtree, we will return the excess number of coins of that subtree : positive means the sum of coins of this subtree is more than the number of nodes of this subtree, negative means the sum of coins of this subtree is less than the number of nodes of this subtree.

So we can traverse this tree by DFS and return the excess number of coins and accumulate the absolute number of excess coins of left subtree and right subtree to the answer.

Python

1
2python
3class Solution:
4    def distributeCoins(self, root):
5        ans = [0]
6        def dfs(node):
7            if not node:
8                return 0
9            left, right = dfs(node.left), dfs(node.right)
10            ans[0] += abs(left) + abs(right)
11            return node.val + left + right - 1
12        dfs(root)
13        return ans[0]

Java

1
2java
3class Solution {
4    int res;
5
6    public int distributeCoins(TreeNode root) {
7        res = 0;
8        dfs(root);
9        return res;
10    }
11
12    private int dfs(TreeNode root) {
13        if (root == null)
14            return 0;
15
16        int left = dfs(root.left);
17        int right = dfs(root.right);
18        res += Math.abs(left) + Math.abs(right);
19        return root.val + left + right - 1;
20    }
21}

JavaScript

1
2javascript
3var distributeCoins = function(root) {
4    let ans = 0;
5
6    const dfs = node => {
7        if (node === null) {
8            return 0;
9        }
10
11        let left = dfs(node.left);
12        let right = dfs(node.right);
13
14        ans += Math.abs(left) + Math.abs(right);
15        return node.val + left + right - 1;
16    }
17
18    dfs(root);
19
20    return ans;
21};

C++

1
2c++
3class Solution {
4public:
5    int distributeCoins(TreeNode* root) {
6        int moves = 0;
7        postOrder(root, moves);
8        return moves;
9    }
10private:
11    int postOrder(TreeNode* root, int & moves) {
12        if(!root)
13            return 0;
14        int left = postOrder(root->left, moves);
15        int right = postOrder(root->right, moves);
16        moves += abs(left) + abs(right);
17        return root->val + left + right - 1;
18    }
19};

C#

1
2csharp
3public class Solution {
4    int ans;
5    public int DistributeCoins(TreeNode root) {
6        ans = 0;
7        dfs(root);
8        return ans;
9    }
10    public int dfs(TreeNode node) {
11        if (node == null) return 0;
12        int L = dfs(node.left);
13        int R = dfs(node.right);
14        ans += Math.Abs(L) + Math.Abs(R);
15        return node.val + L + R - 1;
16    }
17}

These codes recursively traverse the tree while keeping a running total of the number of moves needed. The dfs function returns the number of coins that need to be moved at each node (either taken or given). It does this by comparing the number of coins at each node (node.val) to the ideal scenario (1 coin at each node), and then adding this difference to the running total of moves required.## The Rundown of these Algorithm Solutions

Given the problem - a tree with each node containing different numbers of coins. The target is to make the number of coins at each node equal, in other words, make sure that each node has just one coin. We are asked to move these coins from node to node on a parent-to-child basis, and in the process try to use the least number of such movements.

The approach used here to solve this interesting problem is: Depth-First Search. In this method, we keep moving through the tree as far as possible along each branch before retracing our paths. In our case, we take each subtree and compute the excess coins that are there or vice-versa, the deficit.

Positivity of the excess number of coins simply means there are more coins than there need to be in the subtree. Negativity, on the other hand, represents a deficit of coins in the subtree. The core of our algorithm is to traverse by Depth-First Search through the tree, summing the absolute excess number of coins in the left and right subtrees, and adding it to our answer.

The solution provided covers codes in six different languages. They are:

Python, Java, JavaScript, C++, C#, and Swift

For example:

The Python solution gets the root of the binary tree and perform DFS on this root node. It recursively traverses down the tree, checking the left and right child of each node, and calculating the excess coins in each subtree. It then adds the absolute values of these excess coins to the total number of moves, and returns it.

In the Java solution, it works similarly to Python, but with a different syntax. The DFS method, for instance, is a separate private method that takes a node as an argument.

The JavaScript version, like Java, similarly creates a separate DFS function inside the main function. It also handles null nodes.

The C++ solution is similar to previous solutions, but it calls the DFS method from another method, postOrder(), which is called from the main method. The postOrder() method traverses the tree in a postorder manner, i.e., checking both subtrees of a node before the node itself.

The C# solution performs DFS similarly to Java and JavaScript, but in C# syntax.

All in all, these solutions offer similar implementation of the Depth-First Search algorithm to solve the problem. Their overall time complexity is O(n), where n is the number of nodes in the tree. This is because each node in the tree is visited once.

Now, you have an understanding of the problem, its step-by-step solution, and the codes in different languages. This should provide a solid basis for you to grasp the occurrence and solution to such problems in future.