Tree sort inserts every element into a binary search tree, then performs an in-order traversal to read them out sorted. Performance hinges entirely on the tree staying balanced — with a self-balancing BST it's O(n log n); with a plain BST and adversarial input it degenerates to O(n²).
| Best | Average | Worst | Space (Worst) |
|---|---|---|---|
Ω(n log n) |
Θ(n log n) |
O(n²) |
O(n) |
Build a BST by inserting each element. An in-order traversal visits left subtree, node, right subtree — yielding keys in ascending order. With random input the tree's expected height is O(log n); with sorted input a plain BST becomes a linked list of height n, and the whole sort becomes O(n²).
class Node:
__slots__ = ("key", "left", "right")
def __init__(self, key):
self.key, self.left, self.right = key, None, None
def insert(root, key):
if root is None:
return Node(key)
if key < root.key:
root.left = insert(root.left, key)
else:
root.right = insert(root.right, key)
return root
def in_order(root, out):
if root is None:
return
in_order(root.left, out)
out.append(root.key)
in_order(root.right, out)
def tree_sort(arr):
root = None
for x in arr:
root = insert(root, x)
out = []
in_order(root, out)
return out
print(tree_sort([3, 6, 1, 8, 2, 9, 4])) # [1, 2, 3, 4, 6, 8, 9]