UL$20/0032$ALGORITHM $1$

function $A1($root$,x)$

$Q=$ new Queue$()$

ENQUEUE $($Q$,$ root$)$

while $!$ ISEMPTY$($Q$)$ do

$t=$PEEK$(Q)$

if $(t==x$

return TRUE

else

ENQUeUe$(Q,$left$(t))$

$,$ right $(t$

DEQUEUE $($Q$)$

end while

return FALSE

end function

Note: the function ENQUEUE only inserts

a new element in the queue if this element

is different from NULL

See the image $as$ reference $of$ two algorithms.

Here are the questions:

$(a)$ see the image

$(b)$ see the image

$($c$)$ What is the task performed by algorithms A$1$ and A$2?$ Don$$t forget to

mention the return values for the different cases $[4]$

$($d$)$ What is the worst$-$case time complexity of A$1?$ Use Theta notation $[1]$ and

explain your reasoning $[3][4]$

$($e$)$ Assuming a fully balanced BST $($a BST with all its levels fully populated$)$ of N

elements, what is the recurrence equation describing the running time of A$2?$

$[4]$

$($f$)$ What is the worst$-$case time complexity of A$2?$ Use Theta notation $[1]$ and

show your workings $[3][4]$

$($g$)$ Which algorithm do you recommend to implement? Why? $[6]$