Binary Tree Online Sort

Binary tree online sort inserts elements into a binary search tree (BST) as they arrive, then produces sorted output via in-order traversal.

You use it when data arrives incrementally and you want ordered queries or final sorted output without a separate sorting phase.

Problem

Given a stream ( x_1, x_2, \dots, x_n ), maintain a structure such that:

• insertion is performed online
• elements can be retrieved in sorted order

Idea

Use a BST invariant:

[ \text{left subtree} < \text{node} \le \text{right subtree} ]

Insert each element into the tree. When needed, perform an in-order traversal to obtain the sorted sequence.

Algorithm

Insertion

insert(root, x):
    if root == null:
        return new_node(x)

    if x < root.value:
        root.left = insert(root.left, x)
    else:
        root.right = insert(root.right, x)

    return root

Traversal

inorder(root):
    if root == null:
        return

    inorder(root.left)
    output(root.value)
    inorder(root.right)

Full procedure

binary_tree_online_sort(stream):
    root = null

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

    inorder(root)

Example

Input stream:

[ [5, 2, 8, 1, 3] ]

BST after insertions:

        5
       / \
      2   8
     / \
    1   3

In-order traversal:

[ [1, 2, 3, 5, 8] ]

Correctness

Insertion maintains the BST invariant. In-order traversal visits nodes in non-decreasing order:

• all values in left subtree are smaller
• node value follows
• all values in right subtree are larger or equal

Thus the traversal produces a sorted sequence.

Complexity

Total:

• average: ( O(n \log n) )
• worst: ( O(n^2) ) (degenerate tree)

Space:

[ O(n) ]

Balanced Variants

Using a balanced tree improves guarantees:

This yields consistent ( O(n \log n) ) total time.

Stability

The method is not stable unless equal keys are augmented with insertion order and comparisons respect it.

When to Use

Use binary tree online sort when:

• data arrives incrementally
• ordered queries are needed during insertion
• a tree structure is already required

For batch sorting, array-based algorithms are usually faster due to better cache behavior.