AlgoViz.
Sorting

Tree Sort

Size:15
Execution Narrative
Step 1 of 71Start
Line 1
Starting Tree Sort on 15 elements. Initializing empty Binary Search Tree.
Comparisons0
Swaps0
Operations0

Overview & Concept

Tree Sort is a sorting algorithm that builds a Binary Search Tree (BST) from the elements of the input array and then performs an In-Order traversal (Left-Root-Right) to emit elements in sorted ascending order. Its performance depends directly on the balance of the resulting search tree.

How It Works

BST Construction: Sequentially inserts each element from the array into a Binary Search Tree.

Binary Search Property: For each node, all keys in its left subtree are smaller, and all keys in its right subtree are greater or equal.

In-Order Traversal: Traverses the constructed BST recursively: visit left child, process current node, visit right child.

Sorted Emission: Due to BST invariants, in-order traversal naturally yields elements in non-decreasing order.

Step-by-Step Execution

1. Initialize Empty BSTCreate an empty root node pointer.
2. Insert All ElementsInsert each array item into the BST following binary search insertion rules.
3. In-Order TraversalPerform Left-Root-Right traversal recursively starting at the root.
4. Populate Output ArrayWrite each visited node value sequentially into the destination array.

Asymptotic Complexity Analysis

MetricBest CaseAverage CaseWorst CaseSpace Complexity
Complexity BoundO(n log n)O(n log n)O(n²)O(n)
ExplanationOptimal input arrangement minimizing operations.Expected time for uniformly distributed randomized inputs.Adversarial degenerate conditions requiring full traversal.Auxiliary memory allocated beyond original input size.

Pseudocode & Invariants

Algorithm Logic
procedure treeSort(A):
  root = null
  for x in A: root = insertBST(root, x)
  idx = 0
  inOrder(root): emit into A[idx++]
  return A
Algorithmic Invariants
  • BST Invariant: For any node X, all keys in X.left < X.val ≤ all keys in X.right.
  • In-Order Sortedness: An in-order walk of a valid BST produces a monotonically non-decreasing sequence.
Correctness Guarantee: Invariants hold true prior to loop entry, are preserved during every iteration, and guarantee correct post-condition upon termination.

Advantages & Disadvantages

Key Advantages

  • •O(n log n) average time complexity with self-balancing tree variants (AVL, Red-Black).
  • •Naturally supports online sorting where data arrives continuously in real time.
  • •Dual data structure utility: provides both a sorted list and an active search index.

Trade-offs & Limitations

  • •Degenerates to O(n²) worst-case time on already-sorted data if unbalanced BST is used.
  • •Requires O(n) pointer memory overhead for tree node child references.

Real-World Applications

Online Streaming Sorters

Processing continuous incoming telemetry feeds where queries and insertions occur concurrently.

Database B-Tree Index Builders

Generating indexed table stores from bulk record data.

Decision Guide: When to Use

Ideal Scenarios

  • ✓When data is arriving incrementally and dynamic sorted lookups are needed.

Consider Alternatives When

  • ✕When maximum memory efficiency is required (use Heap Sort or Quick Sort).

Explore Related Algorithms

Compare trade-offs and complexity across complementary tools in AlgoViz.

Heap SortBinary SearchQuick Sort