In-place Conversion of Sorted DLL to Balanced BST in C

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

// Structure to represent a Doubly Linked List (DLL) node
struct DLLNode {
    int data;
    struct DLLNode* prev;
    struct DLLNode* next;
};

// Structure to represent a Binary Search Tree (BST) node
struct BSTNode {
    int data;
    struct BSTNode* left;
    struct BSTNode* right;
};

// Function to create a new DLL node
struct DLLNode* createDLLNode(int data) {
    struct DLLNode* newNode = (struct DLLNode*)malloc(sizeof(struct DLLNode));
    if (newNode) {
        newNode->data = data;
        newNode->prev = newNode->next = NULL;
    }
    return newNode;
}

// Function to insert a DLL node at the end
void insertAtEnd(struct DLLNode** head, int data) {
    struct DLLNode* newNode = createDLLNode(data);
    if (*head == NULL) {
        *head = newNode;
    } else {
        struct DLLNode* current = *head;
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = newNode;
        newNode->prev = current;
    }
}

// Function to find the middle node of a DLL
struct DLLNode* findMiddle(struct DLLNode* head) {
    if (head == NULL)
        return NULL;

    struct DLLNode* slow = head;
    struct DLLNode* fast = head;

    while (fast->next != NULL && fast->next->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }

    return slow;
}

// Function to convert a sorted DLL to a balanced BST
struct BSTNode* sortedDLLToBST(struct DLLNode** head) {
    if (*head == NULL)
        return NULL;

    // Find the middle node
    struct DLLNode* middle = findMiddle(*head);

    // Create a BST node with the middle node's data
    struct BSTNode* root = (struct BSTNode*)malloc(sizeof(struct BSTNode));
    if (root) {
        root->data = middle->data;
        root->left = NULL;
        root->right = NULL;

        // Recursively convert the left and right halves of the DLL
        if (middle->prev != NULL) {
            middle->prev->next = NULL;
            root->left = sortedDLLToBST(head);
        }

        if (middle->next != NULL) {
            middle->next->prev = NULL;
            root->right = sortedDLLToBST(&(middle->next));
        }
    }

    return root;
}

// Function to perform an in-order traversal of a BST
void inorderTraversal(struct BSTNode* root) {
    if (root == NULL)
        return;

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

// Function to free memory allocated for the DLL
void freeDLL(struct DLLNode* head) {
    while (head != NULL) {
        struct DLLNode* temp = head;
        head = head->next;
        free(temp);
    }
}

// Function to free memory allocated for the BST
void freeBST(struct BSTNode* root) {
    if (root == NULL)
        return;

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

int main() {
    struct DLLNode* head = NULL;

    // Insert elements into the sorted DLL
    insertAtEnd(&head, 1);
    insertAtEnd(&head, 2);
    insertAtEnd(&head, 3);
    insertAtEnd(&head, 4);
    insertAtEnd(&head, 5);
    insertAtEnd(&head, 6);
    insertAtEnd(&head, 7);

    printf("Original DLL: 1 2 3 4 5 6 7\n");

    // Convert the DLL to a balanced BST
    struct BSTNode* root = sortedDLLToBST(&head);

    printf("In-order traversal of BST: ");
    inorderTraversal(root);
    printf("\n");

    // Free memory
    freeDLL(head);
    freeBST(root);

    return 0;
}