Tree Sort: Mechanism, Complexity Analysis & Interactive Visualizer

Tree Sort

An elegant tree-based algorithm: build a Binary Search Tree (BST) from the elements, then retrieve them in sorted order using an in-order traversal.

How it works

Tree Sort utilizes a Binary Search Tree data structure to organize and retrieve data. The algorithm follows a simple two-phase procedure:

1. BST Construction Phase: Iterate through the input array and insert each element one by one into a Binary Search Tree. For each node, elements smaller go to the left subtree, and elements larger or equal go to the right subtree.
2. Retrieval Phase: Perform an in-order traversal (Left, Root, Right) of the constructed BST. Because of the BST property, this traversal visits all elements in non-decreasing sorted order, copying them back to the original array.

Complexity

Interactive visualization

Pseudocode

procedure treeSort(A):
  root ← null
  for each x in A:
    root ← insert(root, x)
  i ← 0
  inOrderTraversal(root, A, i)

procedure insert(node, x):
  if node is null:
    return new Node(x)
  if x < node.value:
    node.left ← insert(node.left, x)
  else:
    node.right ← insert(node.right, x)
  return node

procedure inOrderTraversal(node, A, ref i):
  if node is not null:
    inOrderTraversal(node.left, A, i)
    A[i] ← node.value
    i ← i + 1
    inOrderTraversal(node.right, A, i)

JavaScript implementation

class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function treeSort(arr) {
  let root = null;
  
  function insert(node, val) {
    if (!node) return new TreeNode(val);
    if (val < node.val) {
      node.left = insert(node.left, val);
    } else {
      node.right = insert(node.right, val);
    }
    return node;
  }
  
  for (let x of arr) {
    root = insert(root, x);
  }
  
  let i = 0;
  function inOrder(node) {
    if (!node) return;
    inOrder(node.left);
    arr[i++] = node.val;
    inOrder(node.right);
  }
  inOrder(root);
  return arr;
}

Pros and cons

When (not) to use it

• Dynamic data streams: Great if you need to maintain a sorted order of incoming data at all times.
• Learning BST operations: Tree Sort serves as a wonderful introduction to tree data structures and recursive traversal.
• Production arrays: Avoid it for sorting in-memory arrays. Algorithms like Quick Sort, Heap Sort, or Timsort are much faster and use O(1) or O(log n) auxiliary space.