0631MediumTreeDepth-First SearchBinary TreeDP on Trees

Levelling Tokens Across The Depot Tree

Tracked in this browser only

Trains the technique from

LeetCode 979Distribute Coins in Binary Tree

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A courier company links its depots into a binary tree. There are n depots and exactly n tokens spread over them, and a depot may currently hold none, one or several tokens.

tree is the level-order picture of the network. tree[0] is the root. After that the entries arrive in pairs: the next pair gives the left child and then the right child of the next node already read, and null marks a child that is not there. Pairs that would be all null at the end of the list may be left off. Each entry that is not null is the number of tokens sitting at that depot.

One move carries a single token along a single link, either down from a depot to one of its children or up from a depot to its parent. Return the smallest number of moves that ends with exactly one token at every depot.

Examples

Example 1

Input: tree = [0, 4, 0, null, null, 1, 0]
Output: 6

The root holds nothing, its left child holds 4, its right child holds nothing, and that right child has two children holding 1 and 0. Send three tokens from the left child up to the root (3 moves), pass two of them to the right child (2 moves), and pass one of those on to its empty child (1 move). Every depot now holds one token, for 6 moves in total.

Example 2

Input: tree = [0, 0, 0, 7, 0, 0, 0]
Output: 16

All 7 tokens start at the leftmost leaf. Carrying six of them up to that leaf's parent, then four of those up to the root, then three of them down into the right branch and one further down to each of its two leaves, settles every depot at one token in 16 moves.

Example 3

Input: tree = [1, 1, 1]
Output: 0

The root and both of its children already hold one token each, so nothing has to move.

Constraints

The number of depots in the tree is n.
1 <= n <= 100
0 <= tree[i] <= n for every entry that is not null.
The entries that are not null add up to n.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def distribute_coins(tree: list) -> int:

Java

public int distributeCoins(Integer[] tree)

The intended approach

Time O(n) — decoding, ordering and the backward sweep each touch every depot once.Space O(n) for the child arrays, the visiting order and the per-depot differences.

Turn the level-order list into arrays holding each depot's left and right child. Build a children-before-parents visiting order with an explicit stack rather than recursion, since the tree may be a chain of 100 depots. Sweeping that order backwards, each depot works out the difference between the tokens available in its whole subtree and the number of depots in it; that difference is what must cross the link to its parent, in one direction or the other. Adding up the size of that difference over every link gives the answer.

Pythonentry point: distribute_coins

def _decode(tree):
    vals = [tree[0]]
    left = [-1]
    right = [-1]
    order = [0]
    head = 0
    i = 1
    n = len(tree)
    while head < len(order) and i < n:
        node = order[head]
        head += 1
        for side in (0, 1):
            if i >= n:
                break
            v = tree[i]
            i += 1
            if v is None:
                continue
            vals.append(v)
            left.append(-1)
            right.append(-1)
            child = len(vals) - 1
            if side == 0:
                left[node] = child
            else:
                right[node] = child
            order.append(child)
    return vals, left, right


def distribute_coins(tree):
    # O(n) time, O(n) space. Decode the list into child-index arrays, then visit
    # the depots children-first using an explicit stack, because a network shaped
    # like a chain of 100 depots would otherwise nest 100 calls. Each depot
    # reports the tokens it holds, plus every report from its children, minus the
    # single token it must keep. The size of that report is how many tokens have
    # to travel over the edge above the depot, so summing those sizes over every
    # edge gives the total number of moves.
    vals, left, right = _decode(tree)
    n = len(vals)
    order = []
    stack = [0]
    while stack:
        node = stack.pop()
        order.append(node)
        if left[node] != -1:
            stack.append(left[node])
        if right[node] != -1:
            stack.append(right[node])
    report = [0] * n
    moves = 0
    for idx in range(len(order) - 1, -1, -1):
        node = order[idx]
        s = vals[node] - 1
        for c in (left[node], right[node]):
            if c != -1:
                s += report[c]
                moves += abs(report[c])
        report[node] = s
    return moves

The obvious version

Treat a full assignment of tokens to depots as a state and run a breadth-first search from the starting assignment, where one step shifts a single token across one link in either direction. The first time the all-ones assignment appears, its distance is the answer. Only usable on tiny trees, since the number of states grows quickly.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def _bfdecode(tree):
    vals = [tree[0]]
    kids = [[]]
    order = [0]
    head = 0
    i = 1
    n = len(tree)
    while head < len(order) and i < n:
        node = order[head]
        head += 1
        for _ in range(2):
            if i >= n:
                break
            v = tree[i]
            i += 1
            if v is None:
                continue
            vals.append(v)
            kids.append([])
            child = len(vals) - 1
            kids[node].append(child)
            order.append(child)
    return vals, kids


def bf_distribute_coins(tree):
    from collections import deque
    vals, kids = _bfdecode(tree)
    n = len(vals)
    edges = []
    for u in range(n):
        for c in kids[u]:
            edges.append((u, c))
            edges.append((c, u))
    start = tuple(vals)
    goal = tuple([1] * n)
    if start == goal:
        return 0
    seen = {start}
    q = deque([(start, 0)])
    while q:
        st, d = q.popleft()
        for a, b in edges:
            if st[a] == 0:
                continue
            nxt = list(st)
            nxt[a] -= 1
            nxt[b] += 1
            nxt = tuple(nxt)
            if nxt == goal:
                return d + 1
            if nxt not in seen:
                seen.add(nxt)
                q.append((nxt, d + 1))
    return -1

How this problem was checked

Reference solution executed against 10 test cases — 10 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in