Question $2(15$ marks$)$

Non$-$linear data structure

We often need to determine whether a particular number exists in a given list of numbers. One

way of course is to simply start at the beginning of the list and check every data point until we find

what we're looking for or exhaust the list. This is fine if we only need to search the list once.

The method above is very inefficient if we need to search the list many times for different

numbers. In this case, a better method is to turn the list into a Binary Search Tree which can be

searched much more quickly than a list.

$($a$)$ Given the list $2,15,7,8,23,10,12,37,4,17,18,20,9,25,14$

$($i$)$ Turn this list into a binary search tree by inserting elements one by one into an empty

tree. Carefully show the process of building this tree step by step.

$($ii$)$ Highlight the path taken through the tree when searching for the number $18.$

$($b$)$ Write a recursive algorithm "SertedListToBST" that accepts a sorted list and converts it into

a balanced Binary Search Tree.