## Tree Sort

Back to Programming

### Description

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.

### Algorithm

``````INPUT: An unsorted array [98,34,12,.........,n]

OUTPUT: A sorted array[12,34,...............,n]

PROCESS:

Step 1: [Take the inputs from the user]

For i=0 to n repeat

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

### Code

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.

1. It is easy to implement and understand.

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