Tree Sort

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²).

1. Overview

Tree sort is a two-phase algorithm. Phase one inserts every element into a binary search tree (BST), where each node's left subtree holds smaller keys and its right subtree holds larger or equal keys. Phase two performs an in-order traversal, which by the BST property visits keys in ascending order. The diagram traces the example from the code below: the input 3, 6, 1, 8, 2, 9, 4 produces a tree of height 4, and the in-order walk emits 1, 2, 3, 4, 6, 8, 9.

Each insertion walks from the root down to a leaf, so its cost equals the depth of the tree. With random input the expected depth is O(log n), making the total O(n log n). The traversal itself is O(n). Tree sort is rarely the fastest way to sort an array, but it is conceptually important: it is exactly what happens when you insert items into an ordered map and then iterate it.

2. Complexity

3. How it works

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²).

4. Python implementation

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]

5. Trade-offs

• O(n log n) average; O(n²) worst with an unbalanced BST.
• Use an AVL or red-black tree for guaranteed O(n log n).
• Stable if insertion places equal keys consistently (e.g. always to the right).
• O(n) extra memory for the tree nodes — almost always loses to mergesort.

6. Worst Case and How to Avoid It

When the input is already sorted (or reverse sorted), each new key becomes a child of the previous one, and the tree degenerates into a chain. The i-th insertion then takes i comparisons and the total is about n squared over two, which is O(n^2). Nearly sorted real-world data triggers this often. The fix is to use a self-balancing tree such as a red-black tree or AVL tree, which performs rotations to keep height O(log n) and guarantees O(n log n) total regardless of input order. Shuffling the input first also gives expected O(n log n) with an unbalanced BST.

7. Worked Example: Balanced Version

In Python, the practical way to get a balanced ordered structure is sortedcontainers.SortedList (a B-tree-like list of lists rather than a binary tree, but with the same O(log n) insertion contract). The iterative traversal below also avoids Python's recursion limit for deep trees:

from sortedcontainers import SortedList   # pip install sortedcontainers

def tree_sort_balanced(items):
    s = SortedList()
    for x in items:          # n inserts, O(log n) each
        s.add(x)
    return list(s)           # in-order iteration

def in_order_iter(root):
    """Iterative in-order traversal of the Node class above."""
    stack, node, out = [], root, []
    while stack or node:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        out.append(node.key)
        node = node.right
    return out

print(tree_sort_balanced([3, 6, 1, 8, 2, 9, 4]))   # [1, 2, 3, 4, 6, 8, 9]

A natural use of this approach is an online sort: elements arrive one at a time, and at any moment you need the sorted view, the k-th smallest element, or a range of keys. A static sort would have to be rerun after every arrival.

8. Comparison with Other Sorts

For a one-off sort of an array, Python's built-in sorted() (Timsort) will beat any hand-written tree sort: it is implemented in C, exploits existing runs, and has better cache behaviour than pointer-based nodes, each of which costs dozens of bytes of overhead.

9. Pitfalls

• Recursive insert and traversal hit RecursionError on degenerate trees of more than about 1000 nodes.
• Duplicate keys must consistently go to one side, or a counter must be kept per node, otherwise duplicates are lost or order becomes unstable.
• Memory overhead: each node object stores a key and two pointers, so a tree of a million integers uses many times the memory of a list.

10. Related Topics

• Red-Black Tree
• Sorting algorithms
• Binary Search

← Back to Algorithms

Featured Videos