C++-এ বাইনারি ট্রি থেকে বাইনারি সার্চ ট্রি (BST) কনভার্ট করুন

1. BT-এর ইনঅর্ডার ট্রাভার্সাল একটি অ্যারেতে সংরক্ষণ করুন।
2. অ্যারেটি সর্ট করুন।
3. আবার ইনঅর্ডার ট্রাভার্সাল করে সর্টেড অ্যারে থেকে ভ্যালু নোডগুলিতে কপি করুন।

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

struct node {
    int data;
    struct node *left;
    struct node *right;
};

void Inordertraversal(struct node* node, int inorder[], int* index_ptr) {
    if (node == NULL) return;
    Inordertraversal(node->left, inorder, index_ptr);
    inorder[*index_ptr] = node->data;
    (*index_ptr)++;
    Inordertraversal(node->right, inorder, index_ptr);
}

int countNodes(struct node* root) {
    if (root == NULL) return 0;
    return countNodes(root->left) + countNodes(root->right) + 1;
}

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

void arrayToBST(int* arr, struct node* root, int* index_ptr) {
    if (root == NULL) return;
    arrayToBST(arr, root->left, index_ptr);
    root->data = arr[*index_ptr];
    (*index_ptr)++;
    arrayToBST(arr, root->right, index_ptr);
}

struct node* newNode(int data) {
    struct node* temp = (struct node*)malloc(sizeof(struct node));
    temp->data = data;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}

void printInorder(struct node* node) {
    if (node == NULL) return;
    printInorder(node->left);
    printf("%d ", node->data);
    printInorder(node->right);
}

int main() {
    struct node* root = NULL;
    root = newNode(17);
    root->left = newNode(14);
    root->right = newNode(2);
    root->left->left = newNode(11);
    root->right->right = newNode(7);
    printf("Inorder Traversal of the binary Tree: \n");
    printInorder(root);
    int n = countNodes(root);
    int* arr = new int[n];
    int i = 0;
    Inordertraversal(root, arr, &i);
    qsort(arr, n, sizeof(arr[0]), compare);
    i = 0;
    arrayToBST(arr, root, &i);
    delete[] arr;
    printf("\nInorder Traversal of the converted BST: \n");
    printInorder(root);
    return 0;
}

Inorder Traversal of the binary Tree: 11 14 17 2 7
Inorder Traversal of the converted BST: 2 7 11 14 17