Week 8

This week we did some practice on LinkedList and learned a new Object called binary search tree. For LinkedList, we implemented the class using insertion, deletion and reversing. Insertion is quite easy because the function of this method is just assign self.front = LListNode(value, self.front), since self.front is the whole LinkedList. Deletion method is also not difficult. However, reversing function is harder because it contains recursion and I cannot completely understand and trace the function.

Binary Search Tree is a new Object that we learned this week. It is a tree that is sorted. In other words, for children on every node, the left child is always smaller than the right child and the their parent is in the middle of the left and right child. This makes some methods of BST more efficient. And we also learned how to write the __str__ method for BST. A string representation of binary search tree is shown as follows.

>>> print(BST([5,3,2,6,7])

                  7

         6

5

         3

                  2

 Inserting method for BST also uses recursion. If the number given is greater than the node, then the function will call inserting method again on the right children. If the number given is less than the node, then the function will call inserting method again on the left children. This continues to happen until there is no children. And we used a helper function in the inserting method to achieve this.