Create a Balanced bst

#include <stdio.h>
#include <stdlib.h>

// Define a structure for a binary tree node
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

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

// Function to perform an inorder traversal and store elements in the array
void storeInorder(struct Node* root, int* arr, int* index) {
    if (root == NULL)
        return;

    storeInorder(root->left, arr, index);
    arr[(*index)++] = root->data;
    storeInorder(root->right, arr, index);
}

// Function to create a balanced BST from a sorted array
struct Node* sortedArrayToBST(int arr[], int start, int end) {
    if (start > end)
        return NULL;

    int mid = (start + end) / 2;
    struct Node* root = newNode(arr[mid]);

    root->left = sortedArrayToBST(arr, start, mid - 1);
    root->right = sortedArrayToBST(arr, mid + 1, end);

    return root;
}

// Function to convert a normal BST to a balanced BST
struct Node* convertToBalancedBST(struct Node* root) {
    int n = 0;
    int index = 0;
    storeInorder(root, NULL, &n);

    int* arr = (int*)malloc(n * sizeof(int));
    storeInorder(root, arr, &index);

    struct Node* newRoot = sortedArrayToBST(arr, 0, n - 1);

    free(arr);
    return newRoot;
}

// Function to insert a node into a 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 if (data > root->data)
        root->right = insert(root->right, data);

    return root;
}

// Function to take input from the user and build a BST
struct Node* buildBST() {
    struct Node* root = NULL;
    int n, data;

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

    printf("Enter the elements of the BST: ");
    for (int i = 0; i < n; i++) {
        scanf("%d", &data);
        root = insert(root, data);
    }

    return root;
}

// Function to perform an inorder traversal and print the tree
void inorderTraversal(struct Node* root) {
    if (root == NULL)
        return;

    inorderTraversal(root->left);
    printf("%d ", root->data);
    inorderTraversal(root->right);
}

// Function to free memory in the tree
void freeTree(struct Node* root) {
    if (root == NULL)
        return;

    freeTree(root->left);
    freeTree(root->right);
    free(root);
}

int main() {
    struct Node* root = buildBST();

    printf("Original BST in inorder traversal: ");
    inorderTraversal(root);
    printf("\n");

    struct Node* balancedRoot = convertToBalancedBST(root);

    printf("Balanced BST in inorder traversal: ");
    inorderTraversal(balancedRoot);
    printf("\n");

    freeTree(root);
    freeTree(balancedRoot);

    return 0;
}