**Tree sort** is a sorting technique that is totally dependent on the data structure of a **binary search tree**. In this sorting technique first, the binary search tree is created from the given data. A binary search tree is a special type of binary tree in which, for each parent node, the left child will be lesser or smaller than the parent node and the right child will be equal or greater than the parent node.

In the case of a **binary search tree**,** the ****inorder traversal** always displays the elements in sorted order. Hence, this property is used in this sorting. After creating the binary search tree, only the inorder traversal is performed to display the array in sorted order.

**PROCEDURE WITH EXAMPLE:**

Suppose there is a **6 elements** array as follows:

Now the array is to be sorted in **ascending order**. So, for that **binary search tree will be created as follows**. The **first element of the array will be inserted as the ****root node**. The tree will be:

The **2nd element** of the array is **32**** which is greater than ****9**, so it will be inserted as the **right child** of the **root node 9**. The tree will be:

The **next element** of the **array is ****5**, so it will **be first compared with ****9**, as it is **lesser than ****9** so it will be inserted as the **left child**** of the tree**. Hence, the new tree will be:

The **next element** of the array is **-2**. First it will be **compared with 9**. As it is **lesser than 9**, it will **move to the ****left sub tree**, then it will be compared with the left child of 9, i.e. **5**. As **-2**** is lesser than ****5** also, then it will be inserted as the **left child of ****5**. The tree will be:

The **next element** of the array is **7** which is to be inserted into the binary search tree. Again the same process of insertion will be performed. As **7**** is lesser than ****9**, it will be inserted in the **left sub tree**, now **7**** is greater than ****5** so it will be **inserted as the** **right child of ****5** and the tree will be.

The **last element** of the array is **23** that is to be inserted into the tree. It will be **compared with the root element ****9**, as it is **greater than 9**, which means it would be inserted into the **right subtree**. Now it will be **compared with ****32**, as **23**** is lesser than ****32**, so it will be **inserted as the left child** of 32. So the final **tree** will be:

The second phase of this sorting is to print the **inorder traversal (Left -> Root -> Right) ****of the above created tree**. Inorder traversal is performed by traversing the left node, then root, and then right node.

**-2, 5, 7, 9, 23, 32**

It is the sorted order of the array.

```
INPUT: An unsorted array [98,34,12,.........,n]
OUTPUT: A sorted array[12,34,...............,n]
PROCESS:
Step 1: [Take the inputs from the user]
Read n
For i=0 to n repeat
Read arr[i]
Step 2: [Create the Binary Search Tree with the array elements]
Create a node of tree structure with the data to be inserted pointed by a node type pointer ‘p’
Set data[p]<-x
Set left[p]<-NULL
Set right[p]<-NULL
Set str<-root
Set ptr<-root
while(ptr≠NULL) repeat
Set str<-ptr
if x<data[ptr] then
Set ptr<-left[ptr]
else
Set ptr<-right[ptr]
[End of ‘while’ loop]
if x<data[str] then
Set left[str]<-p
else
Set right[str]<-p
[End of function to create the search tree]
Step 3: [Inorder traversal of tree]
if root≠NULL then
Call inorder(left[root]) i.e. For the left sub tree
Print data[root]
Call inorder(right[root]) i.e. For the right sub tree
[End of the function ‘inorder’]
Step 4: [Sort function to call the above two functions]
Create the root node with the first element of the array by setting data[root]<-arr[0]
Set left[root]<-NULL
Set right[root]<-NULL
For i=1 to n repeat
Call insert_node(arr[i]) function to insert the element into the search tree
Print the sorted array by calling ‘inorder(root)’ function
```

__CHARACTERISTICS:__

**1.** This sorting technique is based on the data structure of a binary search tree.

**2.** The sorting procedure has two parts-

**i)** Creating the search tree with the elements of the array,

**ii)** Print the inorder traversal of the array.

__TIME COMPLEXITY:__

The complexity to **insert an element in a binary search tree is ****O(log n)**, so for inserting **n elements**** in the search tree the time complexity will be: ****O(n*log n)**.

If the elements are in **random order and uniformly distributed** i.e. almost half of the elements are lesser than the root node and the rest are equal or greater then there will be an almost similar number of nodes in both subtrees, i.e. **the left and right subtree**.

__SPACE COMPLEXITY:__

The **space complexity of this algorithm is ****O(n)** for **n number of elements**. Because for sorting n elements n extra nodes should be created to create the binary search tree and sort the elements.

__ADVANTAGES:__

**1.** It is easy to implement and understand.

**2.** More efficient than bubble sort or selection sort in the best case.

__DISADVANTAGES:__

**1.** By using an array only it cannot be sorted. The structure should be used to sort the data, as it will be needed to create the tree.

Related

- Bubble Sort
- Selection Sort
- Insertion Sort
- Quick Sort using recursion
- Quicksort Iterative
- Merge Sort using recursion
- Merge Sort Iterative
- 3 way Merge Sort
- Heap Sort using recursion
- Heap Sort Iterative
- Radix Sort for positive integer
- Bucket Sort
- Counting Sort
- Cocktail Sort
- Intro Sort
- Minmax Sort
- List Sort
- Shell Sort
- Gnome sort
- Comb Sort
- Bitonic Sort
- Tim Sort

Contributed by