#include <stdio.h>
#include <stdlib.h>
// Define structure for tree node
struct Node {
    int data;
    struct Node *left, *right;
};

// Create a new node
struct Node* newNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->left = node->right = NULL;
    return node;
}

// Insert a node into BST
struct Node* insert(struct Node* root, int data) {
    if (root == NULL)
        return newNode(data);

    if (data < root->data)
        root->left = insert(root->left, data);
    else
        root->right = insert(root->right, data);

    return root;
}

// Inorder traversal (gives sorted order)
void inorder(struct Node* root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}

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

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

    // Print sorted order
    printf("Sorted array: ");
    inorder(root);
}

int main() {
    int n,arr[20],i;

    printf("Enter number of elements: ");
    scanf("%d", &n);

    printf("Enter %d integers:\n", n);
    for (i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    treeSort(arr, n);

    return 0;
}