data_structures.binary_tree.distribute_coins

Author : Alexander Pantyukhin Date : November 7, 2022

Task: You are given a tree root of a binary tree with n nodes, where each node has node.data coins. There are exactly n coins in 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.

Example 1:

3

/ 0 0

Result: 2

Example 2:

0

/ 3 0

Result 3

leetcode: https://leetcode.com/problems/distribute-coins-in-binary-tree/

Implementation notes: User depth-first search approach.

Let n is the number of nodes in tree Runtime: O(n) Space: O(1)

Classes

CoinsDistribResult
TreeNode

Functions

distribute_coins(→ int)

Module Contents

class data_structures.binary_tree.distribute_coins.CoinsDistribResult

Bases: NamedTuple

excess: int

moves: int

class data_structures.binary_tree.distribute_coins.TreeNode

data: int

left: TreeNode | None = None

right: TreeNode | None = None

data_structures.binary_tree.distribute_coins.distribute_coins(root: TreeNode | None) → int

>>> distribute_coins(TreeNode(3, TreeNode(0), TreeNode(0)))
2
>>> distribute_coins(TreeNode(0, TreeNode(3), TreeNode(0)))
3
>>> distribute_coins(TreeNode(0, TreeNode(0), TreeNode(3)))
3
>>> distribute_coins(None)
0
>>> distribute_coins(TreeNode(0, TreeNode(0), TreeNode(0)))
Traceback (most recent call last):
 ...
ValueError: The nodes number should be same as the number of coins
>>> distribute_coins(TreeNode(0, TreeNode(1), TreeNode(1)))
Traceback (most recent call last):
 ...
ValueError: The nodes number should be same as the number of coins