We can sort a given set of \(n\) numbers by first building a binary search tree consisting of these numbers. Suppose we use insert
to insert the numbers one by one. We then use inorder_walk
to print them in order. What is the worstcase and bestcase running times of this sorting algorithm respectively?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17  def insert(T,z):
'inserts a node z onto a binary search tree T'
y = None
x = T.root
while x != None:
y = x
if z.key < x.key:
x = x.left
else:
x = x.right
z.p = y
if y == None:
T.root = z
elif z.key < y.key:
y.left = z
else:
y.right = z

 def inorder_walk(x):
if x != None:
inorder_walk(x.left)
print x.key
inorder_walk(x.right)
