data_structures.binary_tree.distribute_coins
============================================

.. py:module:: data_structures.binary_tree.distribute_coins

.. autoapi-nested-parse::

   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
-------

.. autoapisummary::

   data_structures.binary_tree.distribute_coins.CoinsDistribResult
   data_structures.binary_tree.distribute_coins.TreeNode


Functions
---------

.. autoapisummary::

   data_structures.binary_tree.distribute_coins.distribute_coins


Module Contents
---------------

.. py:class:: CoinsDistribResult

   Bases: :py:obj:`NamedTuple`


   .. py:attribute:: excess
      :type:  int


   .. py:attribute:: moves
      :type:  int


.. py:class:: TreeNode

   .. py:attribute:: data
      :type:  int


   .. py:attribute:: left
      :type:  TreeNode | None
      :value: None



   .. py:attribute:: right
      :type:  TreeNode | None
      :value: None



.. py:function:: 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