# Binary Tree Online Sort

# 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

```id="n2k8p4"
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

```id="r6m1t9"
inorder(root):
    if root == null:
        return

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

### Full procedure

```id="t9v3x7"
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

| operation | average       | worst    |
| --------- | ------------- | -------- |
| insertion | ( O(\log n) ) | ( O(n) ) |
| traversal | ( O(n) )      | ( O(n) ) |

Total:

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

Space:

[
O(n)
]

## Balanced Variants

Using a balanced tree improves guarantees:

| structure      | insertion              |
| -------------- | ---------------------- |
| AVL tree       | ( O(\log n) )          |
| Red-black tree | ( O(\log n) )          |
| Treap          | expected ( O(\log n) ) |

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.