Lab 2 linked list and a binary tree

To solve a problem, one often considers different ways to represent the relevant data. In some instances, the data might reasonably be placed in a sequence or the data might naturally dictate a hierarchy. This lab introduces the basic structure of and operations on two of the most common data structures: a linked list and a binary tree.

   1 - Linked List
A linked list is either
- Empty; or
- A pair containing some *value* and the *rest* of the list

One realization of this definition in Python is the following class to represent pairs and, for instance, the use of *"mt"* to represent Empty (because we need something to stand for nothing).
```
class Pair:
   def __init__(self, value, rest):
      self.value = value
      self.rest = rest
      boilerplate omitted
```
One can use instances of this class to create a list of the numbers **7** ,**4** ,**2** ,**19** ,**42** (in this order) as follows.

**Pair(7, Pair(4, Pair(2, Pair(19, Pair(42, "mt")))))**

This explicit form is useful at this point to emphasize the structure of the data. Working with longer lists, say of millions of elements, will require building a list incrementally, and we will get there.
    1.1 - Operations
In the file named *"list_ops.py"*, write a data definition for a *NumList*, as we did in class.

Next, follow the design recipe (data definitions if necessary, signature, purpose statement, header, test cases, fill in body) to design the following functions. Your test cases must use the *unittest* module; place your test cases in a single *TestCase* class at the bottom of the file

**Note**: Your goal is not to just implement these operations so that they pass some test cases. Pay particular attention to the structure of the data, the similarities between the functions that you are writing, and how the code is structured in a manner similar to the data (especially when written recursively, and even more so for binary trees).

Finally, none of these functions require value mutation. Don’t use value mutation to solve any of these problems.

1. **length**: Define a function named *length* that takes a linked list and returns the number of values in the list.

2. **sum**: Define a function named *sum* that takes a linked list of numeric values and returns the sum of the values in the list.

3. **count_greater_than**: Define a function named *count_greater_than* that takes a linked list and a threshold value, and that returns the number of values in the list strictly greater than the threshold (e.g., the number of values in the sample list above that are greater than 10).

4. **find**: Define a function named *find* that takes a linked list and a value to find, and that returns the position within the list where the given value appears (where the first value in a non-empty list is at position 0). If the given value does not appear in the list, return None. (Hint: this function is easier with an accumulator.)

5. **sub_one_map**: Define a function named *sub_one_map* that takes a linked list, and returns a new linked list where each number is smaller by one.

6. **insert**: Define a function named *insert* that accepts a *NumList* in *ascending, sorted* order and a new number, and returns a new list containing the new number in the proper location.

   2 - Binary Tree
A binary tree is either
- Empty; or
- A node containing some *value*, a *left* subtree, and a *right* subtree

One realization of this definition in Python is the following class to represent tree nodes and, again, the use of *"mt"* to represent empty.


```
class TreeNode:
   def __init__(self, value, left, right):
      self.value = value
      self.left = left
      self.right = right
     boilerplate omitted
```
One can use instances of this class to create the pictured tree as follows.

```
TreeNode(4,
   TreeNode(9,
      TreeNode(19, "mt", "mt"),
      TreeNode(2, TreeNode(103, "mt", "mt"), "mt")
   ),
TreeNode(42, "mt", TreeNode(7, "mt", "mt"))
)
```

This explicit form is useful at this point to emphasize the structure of the data. Working with larger trees, say of millions of elements, will require building the tree incrementally (and defining how/where elements are added to the tree); as with lists, we will get there.

    2.1 - Operations
In a file named *tree_ops.py*, develop the class definition for a binary tree of numbers, add it to the appropriate section, and implement each of the following operations. Follow the design recipe (data definitions if necessary, signature, purpose statement, header, test cases, fill in body) to design these functions. Your test cases must use the *unittest* module; place your test cases in a single *TestCase* class at the bottom of the file.
size Define a function named size that takes a binary tree and returns the number of the elements in the tree.

**num_leaves**: Define a function named *num_leaves* that takes a binary tree and returns the number of the leaves (i.e., those nodes with both subtrees empty) in the tree.

**sum Define**: a function named *sum* that takes a binary tree of numeric values and returns the sum of the values in the tree.

**height**: Skip this function! Freebie! Go get a lemonade.

**has_triple**: Define a function named *has_triple* that returns true exactly when a tree node (anywhere in the tree) with value n contains an immediate child node with value 3n.

**sub_one_map**: Define a function named *sub_one_map* that returns a new tree where each value is smaller by one. Yes, this is just like the list function.

   3 - Lab Credit
You must submit your files for grading to receive credit for this lab. This requires that you use the specified file names (listed below) and the specified function names for the required operations (review the lab description to verify that these match).

Recall that the file names are as follows.

- *"list_ops.py"* – linked list operations
- *"tree_ops.py"* – binary tree operations