write a c++ program to Tree sort

  
 

// C++ program to implement Tree Sort 

#include <   iostream   >
#include< bits/stdc++.h > 
 

struct Node 
{ 
	int key; 
	struct Node *left, *right; 
}; 

// A utility function to create a new BST Node 
struct Node *newNode(int item) 
{ 
	struct Node *temp = new Node; 
	temp->key = item; 
	temp->left = temp->right = NULL; 
	return temp; 
} 

// Stores inoder traversal of the BST 
// in arr[] 
void storeSorted(Node *root, int arr[], int &i) 
{ 
	if (root != NULL) 
	{ 
		storeSorted(root->left, arr, i); 
		arr[i++] = root->key; 
		storeSorted(root->right, arr, i); 
	} 
} 

 


Node* insert(Node* node, int key) 
{ 
	 
	if (node == NULL) return newNode(key); 
 
	if (key < node->key) 
		node->left = insert(node->left, key); 
	else if (key > node->key) 
		node->right = insert(node->right, key); 
 
	return node; 
} 

// This function sorts arr[0..n-1] using Tree Sort 

void treeSort(int arr[], int n) 
{ 
	struct Node *root = NULL; 

	// Construct the BST 
	root = insert(root, arr[0]); 
	for (int i=1; i< n; i++) 
		root = insert(root, arr[i]); 

	// Store inoder traversal of the BST 
	// in arr[] 
	int i = 0; 
	storeSorted(root, arr, i); 
} 

// Driver Program to test above functions 
int main() 
{ 
	//create input array 
	int arr[] = {5, 4, 7, 2, 11}; 
	int n = sizeof(arr)/sizeof(arr[0]); 

	treeSort(arr, n); 

		for (int i=0; i< n; i++) 
	cout << arr[i] << " "; 

	return 0; 
}