CS2040s : Tutorial 3: BST

Q1
Worst Time Case:
n^4
search all 4 cases

Improved:

iterate a
iterate b
list sum

iterate c
Iterate d
list sum

Search for a possible 100

O(n^2)

Q2
a)
- Easiest: O(n) time and space
We do a inorder traversal, and put it in the linked list

- Improved: Rotate right, till theres no left child
 if theres no left child, go to the right child and rotate
O(n) //traversal, rotation O(1)
O(1) //space

b)
- Easiest :
Recursion, find median and continue
O(nlogn)
Space(logn) //recursion stack

- Improved:

2T(n/2) + o(1)
Make a function that will take in a List and n
The function will return connect the mid with the left tree and right tree recursively while passing n which is taking the number of elements of the list

Find mid, do a recursive step of building the left and right tree.
To build left,
Take first n/2 elements and put in function
To build right.
Take the n- n/2 - 1 elements of the right and put in function

The base case is when n =0 , return value iteself
recursive step
add(left) , add(mid) , add(right)