Distribute Coins in Binary Tree - Practice Coding Problems

Distribute Coins in Binary Tree - Problem

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.

Input & Output

Example 1 — Basic Imbalanced Tree

$ Input: root = [3,0,0]

› Output: 2

💡 Note: Root has 3 coins, both children have 0. Move 1 coin from root to each child: root→left (1 move), root→right (1 move). Total: 2 moves.

Example 2 — Already Balanced

$ Input: root = [1,1,1]

› Output: 0

💡 Note: Each node already has exactly 1 coin. No moves needed.

Example 3 — Complex Distribution

$ Input: root = [1,0,2]

› Output: 2

💡 Note: Left child needs 1 coin, right child has 1 extra. Move 1 coin from right to root (1 move), then from root to left (1 move). Total: 2 moves.

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.

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Binary tree with uneven coin distribution

Calculate Flows

Determine coin excess/deficit for each subtree

Count Moves

Sum absolute coin flows through edges

Key Takeaway

🎯 Key Insight: The minimum moves equals the sum of absolute coin excess flowing through each tree edge during redistribution.

Asked in

G Google 15 a Amazon 12 f Facebook 8 M Microsoft 6

The optimal solution uses DFS to calculate coin excess in each subtree. The key insight is that the minimum moves equals the sum of absolute excess coins flowing through each edge. Time: O(n), Space: O(h) where h is tree height.

Common Approaches

Approach	Time	Space	Notes
✓ DFS with Balance Calculation	O(n)	O(h)	Use DFS to calculate coin excess/deficit at each node and count required moves
Brute Force - Try All Move Sequences	O(k^m)	O(n)	Simulate all possible sequences of coin moves between adjacent nodes

DFS with Balance Calculation — Algorithm Steps

DFS traversal from leaves to root
Calculate excess coins for each subtree
Count moves as sum of absolute excess flowing through edges
Return total moves needed

Visualization

Tap to expand

Step-by-Step Walkthrough

Bottom-Up DFS

Start from leaves, calculate excess for each subtree

Count Moves

Sum absolute excess flowing through each edge

Return Total

Total moves equals sum of all coin flows

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

int totalMoves;

int dfs(struct TreeNode* node) {
    if (!node) return 0;
    
    int leftExcess = dfs(node->left);
    int rightExcess = dfs(node->right);
    
    totalMoves += abs(leftExcess) + abs(rightExcess);
    
    return node->val + leftExcess + rightExcess - 1;
}

int solution(struct TreeNode* root) {
    if (!root) return 0;
    
    totalMoves = 0;
    dfs(root);
    return totalMoves;
}

struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // For demonstration with simple test case
    struct TreeNode* root = createNode(3);
    root->left = createNode(0);
    root->right = createNode(0);
    
    int result = solution(root);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Visit each node exactly once in DFS traversal

✓ Linear Growth

Space Complexity

O(h)

Recursion stack depth equals tree height h

✓ Linear Space

156.0K Views

Medium Frequency

~25 min Avg. Time

3.4K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

DFS with Balance Calculation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler