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.

Algorithm:

```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++

 `// C++ program to implement Tree Sort ` `#include ` ` `  `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

Java

 `// 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 ` `    ``GFG()  ` `    ``{  ` `        ``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``)  ` `        ``{ ` `            ``inorderRec(root.left); ` `            ``System.out.print(root.key + ``" "``); ` `            ``inorderRec(root.right); ` `        ``} ` `    ``} ` `    ``void` `treeins(``int` `arr[]) ` `    ``{ ` `        ``for``(``int` `i = ``0``; i < arr.length; i++) ` `        ``{ ` `            ``insert(arr[i]); ` `        ``} ` `         `  `    ``} ` ` `  `    ``// Driver Code ` `    ``public` `static` `void` `main(String[] args)  ` `    ``{ ` `        ``GFG tree = ``new` `GFG(); ` `        ``int` `arr[] = {``5``, ``4``, ``7``, ``2``, ``11``}; ` `        ``tree.treeins(arr); ` `        ``tree.inorderRec(tree.root); ` `    ``} ` `} ` ` `  `// This code is contributed ` `// by Vibin M `

Output:

```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)

References:
https://en.wikipedia.org/wiki/Tree_sort