jain12

convert a sorted singly linked list into balanced BST

Mar 31st, 2020
83
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.88 KB | None | 0 0
  1. #include<iostream>
  2. using namespace std;
  3.  
  4. class Node {
  5.   public:
  6.     int data;
  7.     Node *next;
  8.   };
  9.  
  10. class TNode{
  11.   public:
  12.      int data;
  13.      TNode *left,*right;
  14.      TNode(int key){
  15.        data=key;
  16.        left=NULL;
  17.        right=NULL;
  18.        }
  19.   };
  20.  
  21. void Inorder(TNode* root){
  22.   if(root==NULL)
  23.     return;
  24.   Inorder(root->left);
  25.   cout<<" "<<root->data;
  26.   Inorder(root->right);
  27.   }
  28.  
  29.  Node* MiddleNode(Node *head,Node* last){
  30.    Node* slow=head,*fast=head;
  31.    while(fast!=last && (fast->next)!=last){
  32.      fast=(fast->next)->next;
  33.      slow=slow->next;
  34.      }
  35.    return slow;
  36.    }
  37.  
  38. TNode* MakeBBST(Node* head,Node *last){
  39.   if(head==last)
  40.     return NULL;
  41.   Node* mid=MiddleNode(head,last);
  42.   TNode *root=new TNode(mid->data);
  43.   if(head==mid)
  44.      mid->next=last;
  45.   root->left=MakeBBST(head,mid);
  46.   root->right=MakeBBST(mid->next,last);
  47.   return root;
  48.   }
  49.  
  50. TNode* ConvertIntoBBST(Node* head){
  51.   if(head==NULL)
  52.     return NULL;
  53.   return MakeBBST(head,NULL);
  54.   }
  55.  
  56. void InsertAfterNode(Node *previous_node_ptr,int key) {
  57.   if(previous_node_ptr==NULL)
  58.     cout<<"previous node is absent";
  59.   else{
  60.     Node *new_node_ptr=new Node;
  61.     new_node_ptr->data=key;
  62.     new_node_ptr->next=previous_node_ptr->next;
  63.     previous_node_ptr->next=new_node_ptr;
  64.     }
  65.   }
  66.  
  67. void InsertFrontNode(Node **head_ref,int key) {
  68.   Node *new_node_ptr=new Node;
  69.   new_node_ptr->data=key;
  70.   new_node_ptr->next=*head_ref;
  71.   *head_ref=new_node_ptr;
  72.   }
  73.  
  74. void Append(Node **head_ref,int key) {
  75.   if(*head_ref==NULL)
  76.     InsertFrontNode(head_ref,key);
  77.   else {
  78.     Node *ptr=*head_ref;
  79.     while(ptr->next!=NULL)
  80.       ptr=ptr->next;
  81.     InsertAfterNode(ptr,key);
  82.     }
  83.   }
  84.  
  85. int main() {
  86.   Node *head;
  87.   head=NULL;
  88.   Append(&head,2);
  89.   Append(&head,3);
  90.   Append(&head,4);
  91.   Append(&head,5);
  92.   TNode *root=ConvertIntoBBST(head);
  93.   Inorder(root);
  94.   return 0;
  95.   }
Add Comment
Please, Sign In to add comment