The ones who are crazy enough to think they can change the world are the ones who do.
- Steve Jobs

Tree Sort

The properties of binary search tree is completely make use of tree sort algorithm. The tree sort algorithm first builds a binary search tree using the elements in an array which is to be sorted and then does an in-order traversal so that the numbers are retrived in a sorted order.

Advantages - Tree Sort

  • The main advantage of tree sort algorithm is that we can make changes very easily as in a linked list.
  • Sorting in Tree sort algorithm is as fast as quick sort algorithm.

Disadvantages - Tree Sort

  • The worst case occur when the elements in an array is already sorted.
  • In worst case, the running time of tree sort algorithm is 0 (n2).

C program - Tree Sort

Here is the program to demonstrate Tree Sort.

tree-sort.c
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
struct node
{
int data;
struct node *left, *right;
};
struct node *root;
void ins(struct node *, int, int);
void inser(struct node *, int);
void display(struct node *);
int main()
{
int choice, no = 0, parentnode;
root = (struct node *) malloc (sizeof(struct node));
printf("\n Enter a number for parent node : ");
scanf("%d",&parentnode);
root -> data = parentnode;
root -> left = root -> right = NULL;
do{
printf("\n 1.Add element");
printf("\n 2.Sort");
printf("\n 3.Exit");
printf("\n Enter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("Enter the element to insert : \n");
scanf("%d",&no);
inser(root, no);
break;
case 2:
printf("\n Sorted elements are : \n");
display(root);
break;
default:
printf("\n Invalid press...");
exit(0);
}
}while(choice < 3);
return 0;
}
void ins(struct node *n, int value, int opt)
{
struct node *t;
t = (struct node *)malloc (sizeof (struct node));
t -> data = value;
t -> left = t -> right = NULL;
if(opt == 1)
n -> left = t;
else
n -> right = t;
printf("%d is inserted",value);
if(opt == 1)
printf(" at the left \n");
else
printf(" at the right \n");
}
void inser(struct node *t,int x)
{
if(t -> data > x)
if(t -> left == NULL)
ins(t,x,1);
else
inser(t -> left, x);
else if(t -> data < x)
if(t -> right == NULL)
ins(t, x, 2);
else
inser(t -> right,x);
else
printf(" Element is already exist in the list ");
}
void display(struct node *p)
{
if(p != NULL)
{
display(p -> left);
printf("%5d",p -> data);
display(p -> right);
}
}
Enter a number for parent node : 5 
1.Add element
2.Sort
3.Exit 
Enter your choice : 1
Enter the element to insert 4
4 is inserted at the left
1.Add element
2.Sort
3.Exit 
Enter your choice : 1
Enter the element to insert 6
6 is inserted at the right
1.Add element
2.Sort
3.Exit 
Enter your choice : 2
Sorted elements are :
4 5 6
1.Add element
2.Sort
3.Exit 
Enter your choice : 3

Report Us

We may make mistakes(spelling, program bug, typing mistake and etc.), So we have this container to collect mistakes. We highly respect your findings.

Report

We to update you