Code:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int val;
struct Node *left, *right;
};
void bstSort(int *arr, int n);
struct Node *insert(struct Node *n, int val);
void storeSorted(struct Node *n, int *arr, int *pos);
void bstDestroy(struct Node *n);
int main()
{
int arr[] = { 10, 5, 8, 20, 16, 70, 50, 9 };
int n = sizeof(arr) / sizeof(arr[0]);
bstSort(&arr, n);
return 0;
}
void bstSort(int *arr, int n)
{
struct Node *root = NULL;
root = insert(root, arr[0]);
for (int i = 1; i < n; i++)
insert(root, arr[i]);
int i = 0;
storeSorted(root, arr, n);
printf("BST is as follows: ");
bstDestroy(root);
}
struct Node *insert(struct Node *n, int val)
{
if (n == NULL) {
// perform binary tree insertion
struct Node *n = (struct Node*)malloc(sizeof(struct Node));
n->val = val;
n->left = NULL;
n->right = NULL;
return n;
}
// right insertion
if(val > (n->val)){
n->right = insert(n->right, val);
}
// left insertion
else{
n->left = insert(n->left, val);
}
return n;
}
void storeSorted(struct Node *n, int *arr, int *pos)
{
int i = pos++;
if (n != NULL) {
storeSorted(n->left, arr, i);
arr[i] = n->val;
storeSorted(n->right, arr, i);
}
}
void bstDestroy(struct Node *n)
{
if (n != NULL){
bstDestroy(n->left);
printf("%d ", n->val);
bstDestroy(n->right);
}
free(n);
}