Searching and Sorting

a$)$ Given the following list of sorted numbers:

$2,18,22,35,57,66,68,72,78,85,89,90,95,97,99$

What comparisons would be made by binary search to find $90$ in this list?

$$What is the worst case scenario for binary search?

b$)$ Given the following list of unsorted numbers:

$45,16,18,6,29,8,4,15$

What would the list look like after two iterations of:

$-$ Selection Sort

$-$ Insertion Sort

$-$ Bubble Sort

$-$ QuickSort

$-$ Merge Sort

Q$2$: Tree

a$)$ Given the following Tree, write the pseudocode pre order, post order, in order, level order traversal with the solution

b$)$ For the following pool draw the Binary Search Tree:

$46815310182012$

Delete the node $4$ and re draw the Binary Search Tree after deleting the node $4.$