Distribute Coins in Binary Tree

Medium
1935.

Distribute Coins in Binary Tree

Distribute Coins in Binary Tree is a medium coding problem on depth-first search and trees, asked in Amazon, Google and Microsoft interviews.

You are given the root of a binary tree with n nodes, where node.val is the number of coins on that node. There are exactly n coins in the whole tree.

In one move you may take one coin from a node and move it to an adjacent node — its parent or one of its children. Return the minimum number of moves needed so that every node holds exactly one coin.

Example 1

Input
root = [3,0,0]
Output
2
Explanation
The root sends one coin to each child: 2 moves.

Example 2

Input
root = [0,3,0]
Output
3
Explanation
The left child sends one coin up to the root and another up and then down to the right child: 1 + 2 = 3 moves.

Example 3

Input
root = [1,0,0,null,3]
Output
4
Explanation
Node 3 passes two coins up to its parent (2 moves), which keeps one and passes the other up to the root (1 move); the root keeps its own coin and passes the arriving one down to its right child (1 move). 4 moves in all.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var distributeCoins = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Distribute Coins in Binary Tree — Problem & Solution

Distribute Coins in Binary Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Distribute Coins in Binary Tree is a medium coding problem on depth-first search and trees, asked in Amazon, Google and Microsoft interviews.

Problem statement

You are given the root of a binary tree with n nodes, where node.val is the number of coins on that node. There are exactly n coins in the whole tree.

In one move you may take one coin from a node and move it to an adjacent node — its parent or one of its children. Return the minimum number of moves needed so that every node holds exactly one coin.

Example 1

Input: root = [3,0,0]
Output: 2
Explanation: The root sends one coin to each child: 2 moves.

Example 2

Input: root = [0,3,0]
Output: 3
Explanation: The left child sends one coin up to the root and another up and then down to the right child: 1 + 2 = 3 moves.

Example 3

Input: root = [1,0,0,null,3]
Output: 4
Explanation: Node 3 passes two coins up to its parent (2 moves), which keeps one and passes the other up to the root (1 move); the root keeps its own coin and passes the arriving one down to its right child (1 move). 4 moves in all.

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

Hints for Distribute Coins in Binary Tree

  1. Hint 1

    Look at a single edge between a node and its parent. How many coins must cross it, in total, whatever else happens?

  2. Hint 2

    The subtree below the edge holds some number of coins and needs exactly as many as it has nodes. The difference — its excess, positive or negative — must cross that edge, and never more than that.

  3. Hint 3

    A post-order DFS can return each subtree's excess (coins − nodes); the answer is the sum of |excess| over all edges.

How to solve Distribute Coins in Binary Tree

Each edge must carry exactly the imbalance of the subtree below it, and an optimal schedule never moves a coin across an edge in both directions. So the minimum is the sum, over every edge, of the absolute excess of the subtree it leads to.

Approach

  1. excess(node): 0 for null. Otherwise compute l = excess(left) and r = excess(right).
  2. Add |l| + |r| to the move count — those many coins cross the two child edges.
  3. Return node.val + l + r - 1: the coins this subtree has minus the one this node keeps (negative means it needs coins from above).
  4. Call excess(root) (the root's own excess is 0) and return the move count.

Why it works

Any valid plan must move at least |excess| coins across an edge, since the subtree below ends with exactly as many coins as nodes. Moving surplus up and deficits down along each edge achieves exactly that many crossings per edge, so the lower bound is met.

Complexity

  • Time — O(n)
  • Space — O(h) for the recursion

Pitfalls

  • Excess can be negative — count its absolute value as moves, but pass the signed value up.
  • Count moves on child edges only; the root has no parent edge.

Reference solution

Python

from typing import Optional

def distributeCoins(root: Optional[TreeNode]) -> int:
    moves = 0

    def excess(node):
        nonlocal moves
        if node is None:
            return 0
        l = excess(node.left)
        r = excess(node.right)
        moves += abs(l) + abs(r)
        return node.val + l + r - 1

    excess(root)
    return moves

Java

public static int distributeCoins(TreeNode root) {
    int[] moves = new int[1];
    excess(root, moves);
    return moves[0];
}

static int excess(TreeNode node, int[] moves) {
    if (node == null) return 0;
    int l = excess(node.left, moves), r = excess(node.right, moves);
    moves[0] += Math.abs(l) + Math.abs(r);
    return node.val + l + r - 1;
}

C++

int coinExcess(TreeNode* node, int& moves);

int distributeCoins(TreeNode* root) {
    int moves = 0;
    coinExcess(root, moves);
    return moves;
}

int coinExcess(TreeNode* node, int& moves) {
    if (!node) return 0;
    int l = coinExcess(node->left, moves), r = coinExcess(node->right, moves);
    moves += abs(l) + abs(r);
    return node->val + l + r - 1;
}

JavaScript

var distributeCoins = function(root) {
    var moves = 0;
    var excess = function(node) {
        if (node === null) return 0;
        var l = excess(node.left), r = excess(node.right);
        moves += Math.abs(l) + Math.abs(r);
        return node.val + l + r - 1;
    };
    excess(root);
    return moves;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals