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 comproblemsdistributecoinsinbinarytree implementation notes user depthfirst search approach let n is the number of nodes in tree runtime on space o1 distributecoinstreenode3 treenode0 treenode0 2 distributecoinstreenode0 treenode3 treenode0 3 distributecoinstreenode0 treenode0 treenode3 3 distributecoinsnone 0 distributecoinstreenode0 treenode0 treenode0 traceback most recent call last valueerror the nodes number should be same as the number of coins distributecoinstreenode0 treenode1 treenode1 traceback most recent call last valueerror the nodes number should be same as the number of coins validation countnodesnone 0 countcoinsnone 0 main calculation getdistribnone namedtuplecoinsdistribresult 0 2 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 validation count_nodes none 0 count_coins none 0 main calculation get_distrib none namedtuple coinsdistribresult 0 2
from __future__ import annotations

from dataclasses import dataclass
from typing import NamedTuple


@dataclass
class TreeNode:
    data: int
    left: TreeNode | None = None
    right: TreeNode | None = None


class CoinsDistribResult(NamedTuple):
    moves: int
    excess: int


def distribute_coins(root: TreeNode | None) -> int:
    

    if root is None:
        return 0

    
    def count_nodes(node: TreeNode | None) -> int:
        
        if node is None:
            return 0

        return count_nodes(node.left) + count_nodes(node.right) + 1

    def count_coins(node: TreeNode | None) -> int:
        
        if node is None:
            return 0

        return count_coins(node.left) + count_coins(node.right) + node.data

    if count_nodes(root) != count_coins(root):
        raise ValueError("The nodes number should be same as the number of coins")

    
    def get_distrib(node: TreeNode | None) -> CoinsDistribResult:
        

        if node is None:
            return CoinsDistribResult(0, 1)

        left_distrib_moves, left_distrib_excess = get_distrib(node.left)
        right_distrib_moves, right_distrib_excess = get_distrib(node.right)

        coins_to_left = 1 - left_distrib_excess
        coins_to_right = 1 - right_distrib_excess

        result_moves = (
            left_distrib_moves
            + right_distrib_moves
            + abs(coins_to_left)
            + abs(coins_to_right)
        )
        result_excess = node.data - coins_to_left - coins_to_right

        return CoinsDistribResult(result_moves, result_excess)

    return get_distrib(root)[0]


if __name__ == "__main__":
    import doctest

    doctest.testmod()