Example: Binary Tree Sorting in C

// Binary Tree Sorting
#include <stdio.h>
#include <stdlib.h> // Required for malloc

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

// Function to create a new node
struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// Function to insert a node into the BST
struct Node* insert(struct Node* root, int value) {
    // If the tree is empty, return a new node
    if (root == NULL) {
        return createNode(value);
    }

    // Otherwise, recur down the tree
    if (value < root->data) {
        root->left = insert(root->left, value);
    } else if (value > root->data) {
        root->right = insert(root->right, value);
    }
    // If value is equal, do not insert duplicates (or handle as per requirement)
    return root;
}

// Function to perform inorder traversal of the BST (Left-Root-Right)
void inorderTraversal(struct Node* root) {
    if (root != NULL) {
        inorderTraversal(root->left);  // Traverse left subtree
        printf("%d ", root->data);     // Visit root node
        inorderTraversal(root->right); // Traverse right subtree
    }
}

// Function to free the memory allocated for the tree
void freeTree(struct Node* root) {
    if (root != NULL) {
        freeTree(root->left);
        freeTree(root->right);
        free(root);
    }
}

int main() {
    // Step 1: Initialize an empty BST
    struct Node* root = NULL;

    // Step 2: Define an array of unsorted numbers
    int arr[] = {50, 30, 70, 20, 40, 60, 80};
    int n = sizeof(arr) / sizeof(arr[0]);

    // Step 3: Insert each element from the array into the BST
    printf("Original array elements: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
        root = insert(root, arr[i]);
    }
    printf("\n");

    // Step 4: Perform inorder traversal to get sorted elements
    printf("Sorted elements (Inorder Traversal): ");
    inorderTraversal(root);
    printf("\n");

    // Step 5: Free allocated memory
    freeTree(root);

    return 0;
}