# Tree Sort

Computer Science Level pending

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 worst-case and best-case 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 

 1 2 3 4 5 def inorder_walk(x): if x != None: inorder_walk(x.left) print x.key inorder_walk(x.right) 

×