Week 9: Binary Search Tree and Running Time Analysis

Hello! Another week for the course blog and some new topics for this week, which include: Binary Search Trees and Running Time Analysis.

This week in lectures, we learned about Binary Search Trees, which are a special type of Tree with the condition that the data in the left sub-tree is less than the data at the root which is less than the data in the right sub-tree. We also learned about was running time analysis, which is how we measure the performance and efficiency of an algorithm by its input size, in order to compare it to others.

The BST data structure allows searches to be more quick and efficient compared to a regular Tree and this is because of how the data is organized. Similar to the Binary Search algorithm, which we learned earlier in the year, the amount steps required in the worst case for a Tree/List would be to search the entire Tree/List, however with the BST/Binary Search algorithm, it is much more efficient and would reduce the number of steps to log(n) where n is the number of elements in the Tree/List.

For this week's lab, it was about BST and my partner and I worked on the method count_less which takes a Tree and value and returns the number of nodes in the Tree that are less than the given value. At first we confused about the different object types and methods. However we were able to finish once we were able to understand the interaction between the BST and BSTNode.