Distribute Coins in Binary Tree

Leetcode Problem 979: Distribute Coins in Binary Tree

Problem Summary

You have a binary tree with n nodes where each node holds some number of coins. The total number of coins equals n (so each node should end up with exactly one). In one move, you can transfer one coin between two adjacent nodes (parent-child). Return the minimum number of moves needed to give every node exactly one coin.

Constraints:

• The tree has between 2 and 100 nodes.
• Each node's value is a non-negative integer.
• The total number of coins across all nodes equals the number of nodes.

Techniques

• Tree
• Depth-First Search
• Binary Tree

Solution

export class TreeNode {
    val: number
    left: TreeNode | null
    right: TreeNode | null

    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val === undefined ? 0 : val)
        this.left = (left === undefined ? null : left)
        this.right = (right === undefined ? null : right)
    }
}

function distributeCoins(root: TreeNode | null): number {
    let moves = 0

    function distribute(root: TreeNode | null): number {
        if (!root) {
            return 0
        }

        const leftExcess = distribute(root.left)
        const rightExcess = distribute(root.right)
        const excess = root.val + leftExcess + rightExcess - 1

        moves += Math.abs(leftExcess) + Math.abs(rightExcess)

        return excess
    }

    distribute(root)

    return moves
}