# Distribute Coins

Distribute Coins is a problem that involves distributing coins among a binary tree's nodes. Each node has a certain number of coins, and the goal is to balance the number of coins in the tree by moving them between nodes. The problem typically asks for the minimum number of moves required to achieve a balanced state.

Example: Let's consider a binary tree with coins assigned to each node. The goal is to determine the minimum number of moves required to balance the number of coins in the tree.

`# Node class definition`

class TreeNode:

def __init__(self, val=0, left=None, right=None):

self.val = val

self.left = left

self.right = right

# Function to distribute coins and calculate minimum moves

def distributeCoins(root):

moves = 0

def dfs(node):

nonlocal moves

if not node:

return 0

left = dfs(node.left)

right = dfs(node.right)

excess = node.val + left + right - 1

moves += abs(excess)

return excess

dfs(root)

return moves

# Create a binary tree

root = TreeNode(3)

root.left = TreeNode(0)

root.right = TreeNode(0)

root.left.right = TreeNode(2)

root.left.right.left = TreeNode(1)

# Distribute coins and calculate minimum moves

min_moves = distributeCoins(root)

print("Minimum moves required:", min_moves)

# Output: 4

In this example, we define a `TreeNode`

class that represents a node in the binary tree. Each node has a value (`val`

), left child (`left`

), and right child (`right`

).

We define the `distributeCoins`

function that takes the root of the binary tree as input and returns the minimum number of moves required to balance the coins in the tree.

Inside the `distributeCoins`

function, we initialize a variable `moves`

to keep track of the minimum moves required.

We define a nested helper function `dfs`

(depth-first search) that performs a depth-first traversal of the tree. The `dfs`

function takes a node as input and returns the excess number of coins in that subtree.

Within the `dfs`

function, we handle the base case where the node is `None`

, in which case we return 0.

We recursively call `dfs`

on the left and right child nodes to calculate the excess number of coins in the left and right subtrees.

We calculate the excess in the current node by adding the coins in the node, left subtree, and right subtree, and subtracting 1 (as we want each node to have 1 coin).

We update the `moves`

variable by adding the absolute value of the excess, as it represents the number of moves required to balance the coins in the current subtree.

Finally, we return the excess value of the current node.

Outside the `dfs`

function, we call `dfs`

on the root of the binary tree to start the traversal and calculate the minimum moves required.

We print the minimum moves, which represents the minimum number of moves required to balance the coins in the tree.

The time complexity of this solution is O(n), where n is the number of nodes in the binary tree, as we need to visit each node once. The space complexity is O(h), where h is the height of the binary tree, as the maximum depth of the call stack during the recursive traversal is determined by the height of the tree.

In this example, we reuse the same binary tree and the `distributeCoins`

function from the previous explanation.

The given binary tree has the following structure:

`3 / \ 0 0 \ 2 / 1`

We call the `distributeCoins`

function with the root of the binary tree.

The function calculates the minimum number of moves required to balance the coins in the tree and returns the result.

In this case, the minimum number of moves required to achieve a balanced state is 4.

The time complexity and space complexity of this solution remain the same as explained earlier: O(n) and O(h), respectively, where n is the number of nodes in the binary tree and h is the height of the tree.