# Solving Leetcode Interviews in Seconds with AI: Distribute Coins in Binary Tree


	# Introduction
	In this blog post, we will explore how to solve the LeetCode problem "979" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like [Chatmagic](https://www.chatmagic.app), we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

	# Problem Statement
	> 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.  

	# Explanation
	Here's a solution to the coin distribution problem in a binary tree, focusing on efficiency and clarity:

*   **High-Level Approach:**
    *   The core idea is to calculate the "demand" or "supply" of coins at each node. A node with `k` coins needs `1 - k` coins to reach the balanced state. If the result is negative, the node has extra coins; if positive, it needs more.
    *   We use a recursive, post-order traversal. For each node, we calculate its demand/supply based on its current value and the demand/supply of its children. The absolute value of the children's demand/supply represents the number of moves needed to balance that subtree.
    *   The total number of moves is the sum of the absolute values of the demand/supply for each node.

*   **Complexity:**
    *   Runtime: O(n), where n is the number of nodes in the tree (single traversal). Storage: O(h), where h is the height of the tree (call stack for recursion). In the worst case (skewed tree), h = n, but on average, it's O(log n) for a balanced tree.

	
	# Code
	```python
	class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def distributeCoins(root):
    moves = 0

    def dfs(node):
        nonlocal moves
        if not node:
            return 0

        left_demand = dfs(node.left)
        right_demand = dfs(node.right)

        moves += abs(left_demand) + abs(right_demand)

        return node.val + left_demand + right_demand - 1

    dfs(root)
    return moves
	```