## Lab 2, CSC 202

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.

Here’s the invitation link for this lab’s repo:

### 1` `Linked List

Empty; or

A pair containing some value and the rest of the list

class Pair: |

def __init__(self, value, rest): |

self.value = value |

self.rest = rest |

# boilerplate omitted |

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

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

EDIT: or global variables. Don’t use those either!

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

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

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

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

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.

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

Empty; or

A node containing some value, a left subtree, and a right subtree

class TreeNode: |

def __init__(self, value, left, right): |

self.value = value |

self.left = left |

self.right = right |

# boilerplate omitted |

TreeNode(4, |

TreeNode(9, |

TreeNode(19, "mt", "mt"), |

TreeNode(2, TreeNode(103, "mt", "mt"), "mt") |

), |

TreeNode(42, "mt", TreeNode(7, "mt", "mt")) |

) |

#### 2.1` `Operations

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

"list_ops.py" – linked list operations

"tree_ops.py" – binary tree operations