====== Homework 02: Binary Tree Properties ======



In this problem, we present a few characteristics of rooted binary trees. First, let us introduce some notation:

    * Each node of a tree stores an integer value named //key//. Let// n// be a node in a //tree T//. We denote by //n.key// the value of the key stored in //n//.
    * By //n.left// and //n.right// and //n.parent// we denote the left and the right child of //n// and the parent node of //n//, respectively.
    * By //n.tree// we denote the subtree of //T// rooted in //n//. The tree //n.tree// contains all nodes //y// with the property that n lies on the path from// y// to the root of// T//. 
    * We denote by //T.root// the root of the tree //T//.
    * By //n.depth// we denote the depth of node n. The depth of the tree root is 0, for any other node// x// it holds, //x.depth// = //x.parent.depth// + 1.


----


Subsequently, we define eight characteristics of nodes and/or (sub)trees:
    - We define the **<fc #ff0000>cost of a tree</fc>** //T// to be the sum of keys in all those nodes of //T// which have exactly two children.
    - We define the **<fc #ff0000>reduced cost of a tree</fc>** //T// to be the sum of all keys in those nodes of //T// which are not leaves. In this characteristics, the root is always considered not to be a leaf.
    - We say that a node n is **<fc #ff0000>L-heavy</fc>** if the number of leaves in //n.left.tree// is bigger than the number of leaves in //n.right.tree//.
    - We say that **<fc #ff0000>dominance</fc>**  of a node x is the number of such nodes y in x.tree for which it holds y.key < x.key.
    - We say that a node //n// is **<fc #ff0000>grandchildren complete</fc>**  if all four grandchildren of n exist. Namely, those are //n.left.left//, //n.left.right//, //n.right.left//, and //n.right.right//.
    - We say that a leaf //n// is a **<fc #ff0000>separated leaf</fc>** if its sibling either does not exist or it is a node which is not a leaf.
    - We say that a node //n// is **<fc #ff0000>case complete</fc>** if //n.tree// contains at least one leaf, and at least one node with two children, and at least one node which has only left child, and at least one node which has only right child.
    - We say that a sequence of nodes //n1//, //n2//, //n3//, ..., //nk// is a **<fc #ff0000>bounded path</fc>** if it contains at least two nodes, //n1// is a leaf, and it also holds: 
        * //nj// = //nj−1.parent// and //nj.key// < //n1.key//, for //j// = 2, ..., //k//.
        * The value of a bounded path is the sum of the keys of all nodes in the bounded path.

----

Finally, we present a recursive specification of a pseudo-random binary tree.

There is a 9-tuple of non-negative integers (LA, RA, M, C0, C1L, C1R, S, D, Rkey), where C0 ≤ C1L ≤ C1R ≤ S.\\
The left and right children of each node //n// and their keys are defined as follows:

    * A value //n.struct// is associated with node //n//. It holds, //n.struct// = ((1 + //n.depth//) × //n.key// × //n.key//) mod M.
    * If //n.struct// < C0 or if //n.depth// = D then node n has no children.
    * If C0 ≤ //n.struct// < C1L then node //n// has only left child.
    * If C1L ≤ n.struct < C1R then node //n// has only right child.
    * If C1R ≤ n.struct < S then node //n// has both left and right children.
    * //T.root.key// = Rkey.
    * If //n.left// exists then //n.left.key// = (LA × //n.key// × //n.key//) mod M.
    * If //n.right// exists then //n.right.key// = (RA × //n.key// × //n.key//) mod M.

==== The Task ====
You are given a 9-tuple (LA, RA, M, C0, C1L, C1R, S, D, Rkey) defining binary tree //T// and one of the eight characteristics given above. Depending on the characteristics, denoted by one of integers 1, 2, 3, 4, 5, 6, 7, 8, calculate the corresponding value:
    - The cost of //T//.
    - The reduced cost of //T//.
    - The number of L-heavy nodes in //T//.
    - The sum of dominances of all nodes in //T//.
    - The number of grandchildren complete nodes in //T//.
    - The number of separated leaves in //T//.
    - The number of case complete nodes in //T//.
    - The maximum value of a bounded path in //T//.


==== Evaluation ====

Your code will be evaluated on 8 test cases. Each test case tests different charactersitics described above.
Each test case consists of 4 separate tests performed on random trees (randomly generated 9-tuple).
Each of the 8 test cases will grant you 0.5 points if all 4 tests pass.
There is time limit 1 second for each test.



==== Starter Code ====
Below is a **basic code structure** you can use. Copy-paste the following code and **complete** the ''solve'' function according to the description above. Then submit your final ''main.py''.


<code python>
def solve(tree_params, characteristics):
    """
    >>> solve((13, 10, 29, 4, 10, 15, 28, 4, 7), 2)
    40    
    >>> solve((11, 19, 29, 6, 13, 20, 30, 5, 14), 3)
    4  
    """
    
</code>


==== Examples ====

|<code>
	 	
__ 7____
28  __26______
     1    __ 3____
        __ 1  __ 3
        13     1
        
</code>|<code>>>> solve((13, 10, 29, 4, 10, 15, 28, 4, 7), 2)
40    </code> The reduced cost of the tree (sum of non-leaf keys) is calculated. |
|<code>
 	
        __________________14______________
  __10________________  ___________*12__________
_*27        _______*15  18____        _______*10
15      ____10____        __ 8____    27____
      __27__  __15__       8  __27__    __18__
      15  18  10  12          15  18    26   8
</code>|<code>>>> solve((11, 19, 29, 6, 13, 20, 30, 5, 14), 3)
4  </code> Number of L-heavy nodes is calculated. L-heavy nodes are marked by '*' in the scheme. |