Tree sort

// C Program 
// Sort array elements by using tree sort
#include <stdio.h>

#include <stdlib.h>
 //Structure of Binary Search Tree node
struct Node
{
	int data;
	struct Node *left, *right;
};
//Adding a new node in binary search tree
void add(struct Node **root, int data)
{
	//Create a dynamic node of binary search tree 
	struct Node *new_node = (struct Node *) malloc(sizeof(struct Node));
	if (new_node != NULL)
	{
		//Set data and pointer values
		new_node->data = data;
		new_node->left = NULL; //Initially node left-pointer is NULL
		new_node->right = NULL; //Initially node right-pointer is NULL
		if ( *root == NULL)
		{
			//When adds a first node in binary tree
			*root = new_node;
		}
		else
		{
			struct Node *find = *root;
			//add new node to proper position
			while (find != NULL)
			{
				if (find->data >= data)
				{
					if (find->left == NULL)
					{
						find->left = new_node;
						break;
					}
					else
					{
						//visit left sub-tree
						find = find->left;
					}
				}
				else
				{
					if (find->right == NULL)
					{
						find->right = new_node;
						break;
					}
					else
					{
						//visit right sub-tree
						find = find->right;
					}
				}
			}
		}
	}
	else
	{
		printf("Memory Overflow\n");
		exit(0); //Terminate program execution
	}
}
//Function which is display arr elements
void display(int arr[], int size)
{
	for (int i = 0; i < size; ++i)
	{
		printf("  %d", arr[i]);
	}
	printf("\n");
}
//Add sorted order elements into array
struct Node *inorder_sort(struct Node *root, int arr[], int *location)
{
	if (root != NULL)
	{
		root->left = inorder_sort(root->left, arr, location);
		//insert tree elements into array
		arr[ *location] = root->data;*location = *location + 1;
		root->right = inorder_sort(root->right, arr, location);
		//Safely remove tree element
		if (root->left == NULL && root->right == NULL)
		{
			//When leaf node found then remove current element
			free(root);
			root = NULL;
		}
	}
	return root;
}
//Executing the tree sort in given array
void tree_sort(int arr[], int size)
{
	int i = 0;
	struct Node *root = NULL;
	for (i = 0; i < size; ++i)
	{
		add( & root, arr[i]);
	}
	i = 0;
	root = inorder_sort(root, arr, & i);
}
int main()
{
	//Define an array of integers
	int arr1[] = {
		3 , 6 , 2 , 5 , -7 , 2 , 1 , 4 , 7 , 8 , 2
	};
	//Get the size of arr
	int size = sizeof(arr1) / sizeof(arr1[0]);
	//Before sort
	printf("\n  Before Sort  :\n");
	display(arr1, size);
	//Sort element
	tree_sort(arr1, size);
	//After sort
	printf("\n  After Sort  :\n");
	display(arr1, size);
	int arr2[] = {
		8 , 2 , 9 , -6 , 3 , 2 , 31 , 41 , 2 , 1 , 67 , 32
	};
	//Get the size of arr
	size = sizeof(arr2) / sizeof(arr2[0]);
	//Before sort
	printf("\n  Before Sort  :\n");
	display(arr2, size);
	//Sort element
	tree_sort(arr2, size);
	//After sort
	printf("\n  After Sort  :\n");
	display(arr2, size);
	return 0;
}

Output

  Before Sort  :
  3  6  2  5  -7  2  1  4  7  8  2

  After Sort  :
  -7  1  2  2  2  3  4  5  6  7  8

  Before Sort  :
  8  2  9  -6  3  2  31  41  2  1  67  32

  After Sort  :
  -6  1  2  2  2  3  8  9  31  32  41  67