Tree Sort

Tree sort sorts a sequence by inserting its elements into a binary search tree, then reading the tree with an inorder traversal. The binary search tree property places smaller values in the left subtree and larger values in the right subtree, so inorder traversal visits values in sorted order.

The algorithm is simple when a binary search tree is already available. Its performance depends heavily on tree balance.

Problem

Given a sequence $A$ of length $n$ , reorder it such that

A[0] \le A[1] \le \cdots \le A[n-1]

Algorithm

Insert each element into a binary search tree. Then traverse the tree inorder.

tree_sort(A):
    root = null

    for x in A:
        root = insert(root, x)

    result = empty list
    inorder(root, result)

    return result

For stable handling of duplicate values, store a count or a list of equal records at each node.

Example

Let

A = [5, 3, 7, 1, 4]

Insert elements into the tree:

Inorder traversal visits:

1, 3, 4, 5, 7

So the sorted result is:

[1, 3, 4, 5, 7]

Correctness

A binary search tree maintains the invariant that all values in the left subtree of a node are less than or equal to the node value, and all values in the right subtree are greater than or equal to the node value. Inorder traversal first visits the left subtree, then the node, then the right subtree. Therefore it outputs all values in nondecreasing order.

Since every input element is inserted into the tree and every node is visited during traversal, the output contains exactly the input elements in sorted order.

Complexity

tree shape	insertion time	traversal time	total time
balanced	$O(n \log n)$	$O(n)$	$O(n \log n)$
degenerate	$O(n^2)$	$O(n)$	$O(n^2)$

Space complexity:

O(n)

The recursion stack for traversal is $O(h)$ , where $h$ is the tree height.

Properties

comparison-based
not in-place
stable only with explicit duplicate handling
efficient with balanced trees
poor on already sorted input if the tree is unbalanced

When to Use

Use tree sort when data is naturally inserted into a tree or when a balanced tree is already part of the system. For arrays, general-purpose sorts such as mergesort, heapsort, or quicksort variants are usually better.

Implementation

class Node:
    def __init__(self, value):
        self.value = value
        self.count = 1
        self.left = None
        self.right = None

def insert(root, value):
    if root is None:
        return Node(value)

    if value < root.value:
        root.left = insert(root.left, value)
    elif value > root.value:
        root.right = insert(root.right, value)
    else:
        root.count += 1

    return root

def inorder(root, out):
    if root is None:
        return

    inorder(root.left, out)
    for _ in range(root.count):
        out.append(root.value)
    inorder(root.right, out)

def tree_sort(a):
    root = None
    for x in a:
        root = insert(root, x)

    result = []
    inorder(root, result)
    return result

type node[T constraints.Ordered] struct {
    value T
    count int
    left  *node[T]
    right *node[T]
}

func insert[T constraints.Ordered](root *node[T], value T) *node[T] {
    if root == nil {
        return &node[T]{value: value, count: 1}
    }

    if value < root.value {
        root.left = insert(root.left, value)
    } else if value > root.value {
        root.right = insert(root.right, value)
    } else {
        root.count++
    }

    return root
}

func inorder[T constraints.Ordered](root *node[T], out *[]T) {
    if root == nil {
        return
    }

    inorder(root.left, out)
    for i := 0; i < root.count; i++ {
        *out = append(*out, root.value)
    }
    inorder(root.right, out)
}

func TreeSort[T constraints.Ordered](a []T) []T {
    var root *node[T]

    for _, x := range a {
        root = insert(root, x)
    }

    result := make([]T, 0, len(a))
    inorder(root, &result)
    return result
}