Tree Sort Algorithm

The Tree Sort algorithm leverages the BST (binary search tree) structure that has elements arranged in an order, such that the in-order traversal of the elements results in a sorted output.

In other words, we can describe the Tree Sort algorithm as:

1. Create a BST from the input array.
2. Perform an in-order traversal (left, root, right).

Before we discuss the implementation, let’s quickly go through the BST properties:

1. Each node can have a maximum of 2 children.
2. The value at each node is more than the value of its left child and less than the value of its right child.

Based on binary search algorithm, the BST is structured to allow fast operations like lookup, insertion or deletion.

The following java implementation represents the overall logic to build a BST from an input array:

public class TreeNode{
    private int value;
    private TreeNode left;
    private TreeNode right;
    TreeNode(int value){
        this.value = value;
    }
}
public TreeNode populateTree(TreeNode root, int element){
    if(null == root){
        // first element
        root = new TreeNode(element);
    } else{
        // otherwise, depending on the root.value
        // and element to be added call the method
        // with either left or right subtree
        if(element < root.value){
            root.left = populateTree(root.left, element);
        } else{
            root.right = populateTree(root.right, element);
        }
    }
    return root;
}

For the first element, we create the root node instance an for other a recursive call is made to the same method with left or right subtree depending on the current value to be appended and the node value.

Using above implementation, we can create a BST for any arbitrary input and then for sorting, we can traverse the array in-order while populating a list of elements along the way.

// driver method
public int[] sort(int[] input){
    TreeNode root = null;
    for(int element : input){
        root = populateTree(root, element);
    }
    var resultList = new ArrayList<Integer>();
    inorder(root, resultList);
    return resultList.stream()
            .mapToInt(Integer::intValue)
            .toArray();
}
// inorder traversal to populate sorted list
public void inorder(TreeNode root, List<Integer> result){
    if(null == root){
        return;
    }
    inorder(root.left, result);
    result.add(root.value);
    inorder(root.right, result);
}

The time taken for an element in a BST is \(O(log_2(n))\) and thus the overall complexity for n elements is \(O(n*log_2(n))\).

One thing to note here about the algorithm runtime is that it depends on the height of the BST which in-turn is dependent on the input. An already sorted input will lead to a BST of height \(n\) and thus the overall runtime in that case becomes \(O(n^2)\).

We can improve the runtime by switching to a self balanced tree like AVL or RedBlack trees.