Tree Sort

Tree sort is a sorting algorithm that is based on Binary Search Tree data structure. It first creates a binary search tree from the elements of the input list or array and then performs an in-order traversal on the created binary search tree to get the elements in sorted order.


Step 1: Take the elements input in an array.
Step 2: Create a Binary search tree by inserting data items from the array into the
        binary search tree.
Step 3: Perform in-order traversal on the tree to get the elements in sorted order.


// C++ program to implement Tree Sort
using namespace std;
struct Node
    int key;
    struct Node *left, *right;
// A utility function to create a new BST Node
struct Node *newNode(int item)
    struct Node *temp = new Node;
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
// Stores inoder traversal of the BST
// in arr[]
void storeSorted(Node *root, int arr[], int &i)
    if (root != NULL)
        storeSorted(root->left, arr, i);
        arr[i++] = root->key;
        storeSorted(root->right, arr, i);
/* A utility function to insert a new
   Node with given key in BST */
Node* insert(Node* node, int key)
    /* If the tree is empty, return a new Node */
    if (node == NULL) return newNode(key);
    /* Otherwise, recur down the tree */
    if (key < node->key)
        node->left  = insert(node->left, key);
    else if (key > node->key)
        node->right = insert(node->right, key);
    /* return the (unchanged) Node pointer */
    return node;
// This function sorts arr[0..n-1] using Tree Sort
void treeSort(int arr[], int n)
    struct Node *root = NULL;
    // Construct the BST
    root = insert(root, arr[0]);
    for (int i=1; i<n; i++)
        insert(root, arr[i]);
    // Store inoder traversal of the BST
    // in arr[]
    int i = 0;
    storeSorted(root, arr, i);
// Driver Program to test above functions
int main()
    //create input array
    int arr[] = {5, 4, 7, 2, 11};
    int n = sizeof(arr)/sizeof(arr[0]);
    treeSort(arr, n);
        for (int i=0; i<n; i++)
       cout << arr[i] << " ";
    return 0;


// Java program to 
// implement Tree Sort
class GFG 
    // Class containing left and
    // right child of current 
    // node and key value
    class Node 
        int key;
        Node left, right;
        public Node(int item) 
            key = item;
            left = right = null;
    // Root of BST
    Node root;
    // Constructor
        root = null
    // This method mainly
    // calls insertRec()
    void insert(int key)
        root = insertRec(root, key);
    /* A recursive function to 
    insert a new key in BST */
    Node insertRec(Node root, int key) 
        /* If the tree is empty,
        return a new node */
        if (root == null
            root = new Node(key);
            return root;
        /* Otherwise, recur
        down the tree */
        if (key < root.key)
            root.left = insertRec(root.left, key);
        else if (key > root.key)
            root.right = insertRec(root.right, key);
        /* return the root */
        return root;
    // A function to do 
    // inorder traversal of BST
    void inorderRec(Node root) 
        if (root != null
            System.out.print(root.key + " ");
    void treeins(int arr[])
        for(int i = 0; i < arr.length; i++)
    // Driver Code
    public static void main(String[] args) 
        GFG tree = new GFG();
        int arr[] = {5, 4, 7, 2, 11};
// This code is contributed
// by Vibin M


2 4 5 7 11

Average Case Time Complexity : O(n log n) Adding one item to a Binary Search tree on average takes O(log n) time. Therefore, adding n items will take O(n log n) time

Worst Case Time Complexity : O(n2). The worst case time complexity of Tree Sort can be improved by using a self-balancing binary search tree like Red Black Tree, AVL Tree. Using self-balancing binary tree Tree Sort will take O(n log n) time to sort the array in worst case.

Auxiliary Space : O(n)


Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

This article is attributed to GeeksforGeeks.org

leave a comment



load comments

Subscribe to Our Newsletter