Binary Search Trees: Convert sorted DLL to Balanced BST

You are given an DLL where the nodes are sorted in ascending order.

we need to construct Balanced BST in-place.

In-place means, no new nodes should be allocated for tree conversion.

Below are the steps to be followed to arrive at the solution:

1. Get the middle of the LL and make it as root.

2. Now recursively do the same for left and right half.

a. Get the middle of left half and make it left child of the root created in step 1.

b. Get the middle of right half and make it right child of the root created in step 1.

#include<iostream>
#include<vector>
#include<string>
#include<unordered_set>

using namespace std;


struct DLL_Node 
{ 
    int data; 
  
    DLL_Node* next; 
  
    DLL_Node* prev; 
};

void DLL_push(DLL_Node** head_ref, int new_data) 
{ 
    DLL_Node* new_node = new DLL_Node();
  
    new_node->data = new_data; 
  
    new_node->prev = NULL; 
  
    new_node->next = (*head_ref); 
  
    if((*head_ref) != NULL) 
    (*head_ref)->prev = new_node ; 
  
    (*head_ref) = new_node; 
} 


void print_inorder(DLL_Node* Node) 
{ 
    if (Node == NULL) 
        return; 
    print_inorder(Node->prev); 
    cout<<" "<<Node->data; 
    print_inorder(Node->next); 
} 

DLL_Node* convert_to_BST(DLL_Node *head)
{
    if(head == NULL || head->next == NULL) 
      return head;

    DLL_Node *slow = head;
    DLL_Node *fast = head;

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

    if(slow->prev != NULL) 
      slow->prev->next = NULL;

    if(slow->next != NULL) 
      slow->next->prev = NULL;
    
    slow->prev = convert_to_BST(head);
    
    slow->next = convert_to_BST(slow->next);
    return slow;
}

int main()
{
     DLL_Node* head = NULL; 
  
    DLL_push(&head, 7); 
    DLL_push(&head, 6); 
    DLL_push(&head, 5); 
    DLL_push(&head, 4); 
    DLL_push(&head, 3); 
    DLL_push(&head, 2); 
    DLL_push(&head, 1);

    DLL_Node *root = convert_to_BST(head); 

    print_inorder(root); 


}

Output:

1 2 3 4 5 6 7