Homework 7

Due Date: Wednesday, October 25th at 11:59 PM

Problem 1: Linked List Class

Write a linked list class called LinkedList. Remember, a singly linked list is made up of nodes each of which contain a value and a pointer. The first node is called the "head node".

Here are the required methods:

  • __init__(self, head) where head is the value of the head node. You could make the head node an attribute.
  • __len__(self): Returns the number of elements in the linked list.
  • __getitem__(self, index) returns the value of the node corresponding to index. Include checks to make sure that index is not out of range and that the user is not trying to index and empty list.
  • __repr__(self) returns LinkedList(head_node).
  • insert_front(self, element) inserts a new node with value element at the beginning of the list.
  • insert_back(self, element) inserts a new node with value element at the end of the list.

Note: An alternative implementation is to create a Node class. You are not required to make a Node class but you may if you prefer that implementation. Please don't steal that implementation from the online forums. I've seen those too.

Problem 2: Binary Tree Class

A binary search tree is a binary tree with the invariant that for any particular node the left child is smaller and the right child is larger. Create the class BinaryTree with the following specifications:

__init__(self): Constructor takes no additional arguments

insert(self, val): This method will insert val into the tree

(Optional) remove(self, val): This will remove val from the tree.

  1. If the node to be deleted has no children then just remove it.
  2. If the node to be deleted has only one child, remove the node and replace it with its child.
  3. If the node to be deleted has two children, replace the node to be deleted with the maximum value in the left subtree. Finally, delete the node with the maximum value in the left-subtree.

getValues(self. depth): Return a list of the entire row of nodes at the specified depth with None at the index if there is no value in the tree. The length of the list should therefore be $2^{\text{depth}}$.

Here is a sample output:

bt = BinaryTree()
arr = [20, 10, 17, 14, 3, 0]
for i in arr:
    bt.insert(i)

print("Height of binary tree is {}.\n".format(len(bt)))
for i in range(len(bt)):
    print("Level {0} values: {1}".format(i, bt.getValues(i)))
Height of binary tree is 4.

Level 0 values: [20]
Level 1 values: [10, None]
Level 2 values: [3, 17, None, None]
Level 3 values: [0, None, 14, None, None, None, None, None]

Note that you do not need to format your output in this way. Nor are you required to implement a __len__ method to compute the height of the tree. I did this because it was convenient for illustration purposes. This example is simply meant to show you some output at each level of the tree.

Problem 3: Peer Evaluations

Evaluate the members of your group for Milestone 1. Please follow the instructions in the provided survey. The survey can be found here: Milestone 1 Peer Evaluation.

Problem 4: Course Evaluation

Please take the Course Evaluation.