i have a data structures assignment in binary search trees please use my class methods and attributes and understand it then answer the questions kindly write for each function a main program to test it after implementing each function

this is the class:

count $=0$

class BST:

class $\_$Node:

def $\_\_$init$\_\_($self$,$ data, left$=$None, right$=$None$)$:

self.$\_$data $=$ data

self.$\_$left $=$ left

self.$\_$right $=$ right

self.$\_$depth $=0$

def $\_\_$str$\_\_($self$)$:

return $\text{'}(\{0\})\text{'}.$format$($self$.\_$data$)$

def $\_\_$init$\_\_($self$)$:

self.$\_$root $=$ None

def clear$($self$)$:

self.$\_$root $=$ None

def isEmpty$($self$)$:

return self.$\_$root is None

def rootVal$($self$)$:

if not self.isEmpty$()$:

return self.$\_$root.$\_$data

else:

raise TypeError$("$None value"$)$

def rootNode$($self$)$:

return self.$\_$root

def insert$($self$,$ val$)$:

newNode $=$ self.$\_$Node$($val$,$ None, None$)$

if self.isEmpty$()$:

self.$\_$root $=$ newNode

return

p $=$ None

c $=$ self.$\_$root

while c is not None:

p $=$ c

if val $>$ c$.\_$data:

c $=$ c$.\_$right

elif val $<$ c$.\_$data:

c $=$ c$.\_$left

else:

return

if val $>$ p$.\_$data:

p$.\_$right $=$ newNode

else:

p$.\_$left $=$ newNode

def $\_\_$contains$\_\_($self$,$ val$)$:

c $=$ self.$\_$root

while c is not None:

if val $==$ c$.\_$data:

return True

if val $<$ c$.\_$data:

c $=$ c$.\_$left

else:

c $=$ c$.\_$right

return False

def containsRec$($self$,$ val$)$:

return self.$\_$containsRec$($val$,$ self.$\_$root$)$

def $\_$containsRec$($self$,$ val, c$)$:

if c is None:

return False

if c$.\_$data $==$ val:

return True

if val $>$ c$.\_$data:

return self.$\_$containsRec$($val$,$ c$.\_$right$)$

else:

return self.$\_$containsRec$($val$,$ c$.\_$left$)$

def minT$($self$)$:

if self.isEmpty$()$:

print$("$Empty$")$ # or raise exception

return

c $=$ self.$\_$root

while c$.\_$left is not None:

c $=$ c$.\_$left

return c$.\_$data

def maxT$($self$)$:

if self.isEmpty$()$:

print$("$Empty$")$ # or raise exception

return

c $=$ self.$\_$root

while c$.\_$right is not None:

c $=$ c$.\_$right

return c$.\_$data

def printIn$($self$)$:

self.$\_$printIn$($self$.\_$root$)$

print$()$

def $\_$printIn$($self$,$ c$)$:

if c is None:

return

self.$\_$printIn$($c$.\_$left$)$

print$($c$.\_$data, end$=",")$

self.$\_$printIn$($c$.\_$right$)$

def printPost$($self$)$:

self.$\_$printPost$($self$.\_$root$)$

print$()$

def $\_$printPost$($self$,$ c$)$:

if c is None:

return

self.$\_$printPost$($c$.\_$left$)$

self.$\_$printPost$($c$.\_$right$)$

print$($c$.\_$data, end$=",")$

def printPre$($self$)$:

self.$\_$printPre$($self$.\_$root$)$

print$()$

def $\_$printPre$($self$,$ c$)$:

if c is None:

return

print$($c$.\_$data, end$=",")$

self.$\_$printPre$($c$.\_$left$)$

self.$\_$printPre$($c$.\_$right$)$

def sumT$($self$)$:

return self.$\_$sumT$($self$.\_$root$)$

def $\_$sumT$($self$,$ c$)$:

if c is None:

return $0$

return self.$\_$sumT$($c$.\_$left$)+$c$.\_$data$+$self.$\_$sumT$($c$.\_$right$)$

def $\_\_$len$\_\_($self$)$:

return self.$\_$count$($self$.\_$root$)$

def $\_$count$($self$,$ c$)$:

if c is None:

return $0$

return self.$\_$count$($c$.\_$left$)+1+$self.$\_$count$($c$.\_$right$)$

# $\%\%$

def $\_\_$str$\_\_($self$)$:

result $=$ DLL$()$

self.$\_$elements$($result$,$ self.$\_$root$)$

return str$($result$)$

def $\_$elements$($self$,$ dll$,$ c$)$:

if c is None:

return

self.$\_$elements$($dll$,$ c$.\_$left$)$

dll$.$addToTail$($c$.\_$data$)$

self.$\_$elements$($dll$,$ c$.\_$right$)$

this is the question note non memeber function write it outside the class:

Sort DLL

Write the implementation of a non$-$member function Sort$($dll$)$ that returns the input dll after sorting it Hint: The idea here is that you need to create a BST from the elements in the given DLL$.$ What

is the complexity of your work?