FOR FREE MATERIALS

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