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:

1. We define the cost of a tree T to be the sum of keys in all those nodes of T which have exactly two children.
2. We define the reduced cost of a tree 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.
3. We say that a node n is L-heavy if the number of leaves in n.left.tree is bigger than the number of leaves in n.right.tree.
4. We say that dominance of a node x is the number of such nodes y in x.tree for which it holds y.key < x.key.
5. We say that a node n is grandchildren complete if all four grandchildren of n exist. Namely, those are n.left.left, n.left.right, n.right.left, and n.right.right.
6. We say that a leaf n is a separated leaf if its sibling either does not exist or it is a node which is not a leaf.
7. We say that a node n is case complete 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.
8. We say that a sequence of nodes n1, n2, n3, …, nk is a bounded path 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.

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:

1. The cost of T.
2. The reduced cost of T.
3. The number of L-heavy nodes in T.
4. The sum of dominances of all nodes in T.
5. The number of grandchildren complete nodes in T.
6. The number of separated leaves in T.
7. The number of case complete nodes in T.
8. The maximum value of a bounded path in T.

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.

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.

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