Distribute Coins In Binary Tree - Leetcode Solution

Problem Statement:

Given the root of a binary tree with N nodes, each node in the tree has node.val coins, and there are N coins total.

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 number of moves required to make every node have exactly one coin.

Solution:

The problem asks us to find the minimum number of moves required to make every node have exactly one coin. In order to achieve this, we can use the fact that each node is allowed to distribute coins to its children as well as its parent.

We can traverse the binary tree in a bottom-up manner, starting from the leaves and moving up towards the root. For each subtree, we can calculate the total number of coins in the subtree and the number of moves required to make each node have exactly one coin. This can be done recursively as follows:

• Recursively calculate the number of coins and the number of moves required to make each node in the left subtree have exactly one coin.
• Recursively calculate the number of coins and the number of moves required to make each node in the right subtree have exactly one coin.
• Calculate the total number of coins in the current subtree as the sum of the number of coins in the left and right subtrees, plus the number of coins in the current node.
• Calculate the number of moves required to make each node in the current subtree have exactly one coin as follows:
  • If the total number of coins in the subtree is one, then no moves are required.
  • Otherwise, the number of moves required is equal to the absolute difference between the total number of coins in the subtree and the number of nodes in the subtree.

We can return the total number of moves required to make every node in the binary tree have exactly one coin as the final answer.

Example:

Let's consider the following binary tree:

     3
   /   \
  0     0

The total number of coins in the tree is 3 + 0 + 0 = 3.

We can start the recursive traversal from the leaves. At the leaf node with value 0, we have one coin and we need to distribute it to its parent. The number of moves required is 1.

Similarly, at the other leaf node with value 0, we have one coin and we need to distribute it to its parent. The number of moves required is 1.

Now, we can move up to the parent node with value 3. The total number of coins in the subtree rooted at this node is 3. Since there are three nodes in the subtree, we need to redistribute two coins in such a way that each node has one coin. This can be achieved by moving one coin from the left child to the parent and one coin from the right child to the parent. The number of moves required is 2.

Therefore, the total number of moves required to make every node have exactly one coin is 1 + 1 + 2 = 4.

Time Complexity:

The time complexity of the above algorithm is O(N), where N is the number of nodes in the binary tree. This is because we visit each node once during the recursive traversal.

Space Complexity:

The space complexity of the above algorithm is O(H), where H is the height of the binary tree. This is because the recursive call stack can have at most H function calls in the worst case when the binary tree is skewed.

1