SLOG #7: Week 9

   This week we have learnt about how to create binary search tree, and discussed about run time analysis during the lectures. Since the exercise # 3 was due this week, our prof taught us how to form a TreeList (list that have structure similar to a Binary Tree) when the correct pre-ordered list and in-ordered list was given. Under the condition when no two nodes have the same values, the root can found in the pre-ordered list as the first element, and the left and right-sub TreeList can be found according the pattern of the lists. Pre-order have root as the first element, all left sub-tree value in pre-order after the root, and  all right sub-tree value in pre-order placed in the list after the last value in the left sub-tree. In-ordered list have root placed after the left sub-tree in-ordered values and before the right sub-tree in-ordered values. With correct slicing on the left and right sub-trees in both ordered list, recursive calls can be made to build up the correct sub-trees and root that can be used to form their corresponding in-order, pre-order lists, and TreeList.

   Binary search tree have the characteristics of a binary tree with the condition that any value less than the root belongs to the left sub-tree, and any value greater than the root belong to the right sub-tree. In this tree, no two nodes have the same value. When searching for a value or inserting a new value, the value will be checked based whether the value is equal, smaller, or greater and go to the corresponding sub-tree branch or stop. Similar terminologies can be applied when deleting a root node value, with conditions made when both children exists for the tree. 

   To search or insert a specific item, binary search tree have similar run time when compared to a binary search algorithm. In the lecture, we discussed how run time on each individual computer is different depending on the processing speed, but it does not affect the numbers of steps it required to process. During the lecture we reviewed both selection sort and insertion sort to demonstrate the run time may depend on both the object analyzed and the algorithm itself.

   In this week’s lab, we worked on creating functions that calls helper function to perform certain tasks that the function itself may not handle. Over all, the code given takes more time to read in order to give a complete understanding on what the required function was supposed to perform than the actual coding. After the lab I realized, from time to time, repetitive codes can be replaced either using inheritance or calling on other functions.