Show problems as
Classic problem #979MediumTreeDepth-First SearchBinary TreeDP on Trees

Distribute Coins in Binary Tree

Real-world version: Levelling Tokens Across The Depot Tree
Tracked in this browser only
Read Distribute Coins in Binary Tree on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def distribute_coins(tree: list) -> int:
Java
public int distributeCoins(Integer[] tree)

More on the same topics