Intro: A tree sort is an algorithm that builds a binary search tree from the elements to be sorted, and then traverses the tree so that the elements come out in sorted order. Its typical use is sorting elements adaptively: after each insertion, the set of elements seen so far is available in sorted order.

The first element becomes the root of the tree. All elements are compared with the root and are separated into those less than the root and those greater than the root.
Building the left and right subtree corresponds to the recursive calls in quicksort. The elements and size of the left and right subtrees are the same as the two partitions.
The first element less than the root becomes the root of the left subtree and all elements in that subtree are separated by the left subtree root. Similarly with the right subtree.

Pseudo Code:

static treenode<RandomAccessIterator>* build(RandomAccessIterator first, RandomAccessIterator last)
    treenode<RandomAccessIterator>* root = NULL;
    for (RandomAccessIterator it = first; it < last; ++it) {
        treenode<RandomAccessIterator>* node = new treenode<RandomAccessIterator>(*it);
        if (root == NULL) {
            root = node;
        else {
            treenode<RandomAccessIterator>* current = root,* previous = NULL;
            bool less;
            while (current != NULL) {
                less = node->value_ < current->value_;
                previous = current;
                current = less ? current->left_ : current->right_;
            if (less) {
                previous->left_ = node;
            else {
                previous->right_ = node;
    return root;