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 my question is write a python function to non memeber function write it outside the class:

Sort DLL

Write the implementation of a nonmember 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?

use this class and watch out the private fields you ca not use them outside the class define setters and getters.

from DLList import DLL

from QueueSLL import QueueSLL

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