Merge Two Balanced Binary Search Trees in C

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

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

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

// Function to perform an in-order traversal of a BST and store nodes in an array
void inOrderTraversal(struct TreeNode* root, struct TreeNode* arr[], int* index) {
    if (root) {
        inOrderTraversal(root->left, arr, index);
        arr[(*index)++] = root;
        inOrderTraversal(root->right, arr, index);
    }
}

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

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

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

    return root;
}

// Function to merge two balanced BSTs
struct TreeNode* mergeBSTs(struct TreeNode* root1, struct TreeNode* root2) {
    // Step 1: Perform in-order traversal of both trees and store nodes in arrays
    struct TreeNode* arr1[100]; // Assuming a maximum of 100 nodes for simplicity
    struct TreeNode* arr2[100];
    int index1 = 0, index2 = 0;

    inOrderTraversal(root1, arr1, &index1);
    inOrderTraversal(root2, arr2, &index2);

    // Step 2: Merge the two sorted arrays into a single sorted array
    struct TreeNode* mergedArr[200]; // Assuming a maximum of 200 nodes for simplicity
    int mergedIndex = 0;

    int i = 0, j = 0;
    while (i < index1 && j < index2) {
        if (arr1[i]->data < arr2[j]->data) {
            mergedArr[mergedIndex++] = arr1[i++];
        } else {
            mergedArr[mergedIndex++] = arr2[j++];
        }
    }

    while (i < index1) {
        mergedArr[mergedIndex++] = arr1[i++];
    }

    while (j < index2) {
        mergedArr[mergedIndex++] = arr2[j++];
    }

    // Step 3: Build a balanced BST from the merged array
    return sortedArrayToBST(mergedArr, 0, mergedIndex - 1);
}

// Function to perform in-order traversal of a BST and print the nodes
void printInOrder(struct TreeNode* root) {
    if (root) {
        printInOrder(root->left);
        printf("%d ", root->data);
        printInOrder(root->right);
    }
}

// Main function
int main() {
    // Create two balanced BSTs
    struct TreeNode* root1 = newNode(1);
    root1->left = newNode(2);
    root1->right = newNode(3);

    struct TreeNode* root2 = newNode(4);
    root2->left = newNode(5);
    root2->right = newNode(6);

    // Merge the two BSTs
    struct TreeNode* mergedRoot = mergeBSTs(root1, root2);

    // Print the in-order traversal of the merged BST
    printf("In-order traversal of the merged BST: ");
    printInOrder(mergedRoot);

    return 0;
}