The subsequent algorithm is straightforward, involving locating the central node within the list and assigning it as the root of the tree under construction.
Make the center of the linked list the new root node.
Go through the same process recursively for both the right and left halves.
- Find the midpoint of the left half and assign it as the left child of the root created in Step 1.
- Identify the middle of the right half and set it as the right child of the root created in Step 1.
The time complexity is O(nLogn), where n represents the quantity of nodes within the Linked List.
Method No. 2 (Tricky)
In this approach, we construct the tree in a different manner compared to Method 1. Instead of building from the roots to the leaves, we start from the leaves and work our way up to the root. The fundamental idea is to insert nodes into the Binary Search Tree (BST) in the exact sequence as they appear in the Doubly Linked List. This ensures that the tree construction can be achieved efficiently within O(n) time complexity.
To initiate the process, we first determine the total number of nodes present in the given Linked List, denoted as 'n'. Subsequently, we select the left n/2 nodes and recursively form the left subtree. Once the left subtree is established, we assign the middle node as the root and link the left subtree to it. Finally, we proceed to recursively construct the right subtree and attach it to the root node.
We persist in advancing the list head pointer to the subsequent node while building the Binary Search Tree to ensure the accurate logic handler in every recursive invocation.
The process of running method 2 is depicted below. The main code responsible for creating a Balanced Binary Search Tree (BST) is explained.
C Program:
#include<stdio.h>
#include<stdlib.h>
struct Node
{
int data;
struct Node* next;
struct Node* prev;
};
int countNodes ( struct Node *head );
struct Node* sortedListToBSTRecur( struct Node **head_ref, int n );
struct Node* sortedListToBST ( struct Node *head )
{
int n = countNodes ( head );
return sortedListToBSTRecur ( &head, n );
}
struct Node* sortedListToBSTRecur ( struct Node **head_ref, int n )
{
if ( n <= 0 )
return NULL;
struct Node *left = sortedListToBSTRecur ( head_ref, n/2 );
struct Node *root = *head_ref;
root -> prev = left;
*head_ref = ( *head_ref ) -> next;
root -> next = sortedListToBSTRecur ( head_ref, n-n/2-1 );
return root;
}
int countNodes ( struct Node *head )
{
int count = 0;
struct Node *temp = head;
while( temp )
{
temp = temp -> next;
count++;
}
return count;
}
void push ( struct Node** head_ref, int new_data )
{
struct Node* new_node =
( struct Node* ) malloc( sizeof ( struct 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 printList ( struct Node *node )
{
while ( node!=NULL )
{
printf ( "%d ", node -> data );
node = node->next;
}
}
void preOrder ( struct Node* node )
{
if ( node == NULL )
return;
printf ( "%d ", node -> data );
preOrder ( node->prev );
preOrder ( node->next );
}
int main ()
{
struct Node* head = NULL;
push ( &head, 14 );
push ( &head, 13 );
push ( &head, 12 );
push ( &head, 11 );
push ( &head, 10 );
push ( &head, 9 );
push ( &head, 8 );
printf ( "Given Linked List\n" );
printList (head);
struct Node *root = sortedListToBST (head);
printf ( "\n PreOrder Traversal of constructed BST \n " );
preOrder (root);
return 0;
}
C++ Program:
#include <bits/stdc++.h>
using namespace std;
class Node1
{
public:
int data;
Node1* next;
Node1* prev;
};
int counttheNodes ( Node1 *head );
Node1* sortedLstToBSTRecur ( Node1 **head_ref, int no );
Node1* sortedLstToBST ( Node1 *head )
{
int no = counttheNodes ( head );
return sortedLstToBSTRecur ( &head, no );
}
Node1* sortedLstToBSTRecur ( Node1 **head_ref, int no )
{
if ( no <= 0 )
return NULL;
Node1 *left = sortedLstToBSTRecur( head_ref, no/2 );
Node1 *root = *head_ref;
root -> prev = left;
*head_ref = ( *head_ref ) -> next;
root -> next = sortedLstToBSTRecur ( head_ref, no-no/2-1 );
return root;
}
int counttheNodes ( Node1 *head )
{
int count = 0;
Node1 *temp = head;
while ( temp )
{
temp = temp -> next;
count++;
}
return count;
}
void push ( Node1** head_ref, int new_data )
{
Node1* new_node = new Node1 ();
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 printtheList ( Node1 *node )
{
while ( node!=NULL )
{
cout << node -> data << " ";
node = node -> next;
}
}
void preOrder ( Node1* node )
{
if ( node == NULL )
return;
cout << node -> data <<" ";
preOrder ( node -> prev );
preOrder ( node -> next );
}
int main ()
{
Node1* head = NULL;
push ( &head, 14 );
push ( &head, 13 );
push ( &head, 12 );
push ( &head, 11 );
push ( &head, 10 );
push ( &head, 9 );
push ( &head, 8 );
cout << "Given Linked List\n";
printtheList ( head );
Node1 *root = sortedLstToBST (head);
cout << "\nPreOrder Traversal of constructed BST \n ";
preOrder (root);
return 0;
}
Output:
Given Linked List
8 9 10 11 12 13 14
PreOrder Traversal of constructed BST
11 9 8 10 13 12 14
Time Complexity will be O(n).