week9

During the lecture, we learn a new concept name Binary Search Tree. The tree is a list.

It is useful I think for example if we want to get a sorted output of all the elements, the best thing to do is sort them when they are inputed.

however, I think it is also a typical way of trading the space for time...

usually, we have a list with n elements, then n+1 address will produced to capture the value.
But when we use BST, 3n+1 is necessary since each node need an address to itself and contains two elements: item and link.