Tree => Doubly Linked List && Singly Linked List => BST

#include <iostream> class Node { public: int data; Node* left; Node* right; Node(int value) : data(value), left(nullptr), right(nullptr) {} }; class TreeToLinkedListConverter { public: // Convert Binary Tree to Doubly Linked List Node* treetoDoubleLinkedList(Node* root) { if (root == nullptr) return nullptr; // Convert left and right subtrees to linked lists Node* rootLeft = treetoDoubleLinkedList(root->left); Node* rootRight = treetoDoubleLinkedList(root->right); // Make the root a circular doubly linked list root->left = root; root->right = root; // Append root and right subtree to the left linked list rootLeft = append(rootLeft, root); rootLeft = append(rootLeft, rootRight); return rootLeft; } // Append a and b doubly linked lists Node* append(Node* a, Node* b) { Node* aLast = a->left; Node* bLast = b->left; join(aLast, b); join(bLast, a); return aLast; } // Join doubly linked lists a and b void join(Node* a, Node* b) { a->right = b; b->left = a; } }; class LinkedListToBSTConverter { public: // Convert Linked List to Balanced Binary Search Tree Node* linkedListToBST(Node** head, int n) { if (*head == nullptr || n <= 0) return nullptr; // Recursively convert left half of linked list to left subtree Node* left = linkedListToBST(head, n / 2); // Create root node and advance head pointer Node* root = new Node(0); // Initialize the root node with a placeholder value root->left = left; root->right = nullptr; root->data = (*head)->data; *head = (*head)->right; // Recursively convert right half of linked list to right subtree root->right = linkedListToBST(head, n - n / 2 - 1); return root; } }; int main() { // Create instances of converters and nodes TreeToLinkedListConverter treeToListConverter; LinkedListToBSTConverter listToTreeConverter; Node* root = new Node(10); // ... Add more nodes and construct the tree // Convert the binary tree to a doubly linked list Node* linkedList = treeToListConverter.treetoDoubleLinkedList(root); // Convert the linked list back to a balanced binary search tree int n = 0; // Determine the number of nodes in the linked list Node* bstRoot = listToTreeConverter.linkedListToBST(&linkedList, n); // Print or perform other operations with the resulting tree // ... return 0; }