Tuesday, August 28, 2012

Convert Singly Linked List to height balanced BST


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

typedef struct node{
 int data;
 struct node *next;
 struct node *left;
}LNode;

LNode* newNode(int data){
 LNode *n = (LNode*)malloc(sizeof(LNode));
 n->data = data;
 n->next = NULL;
 n->left = NULL;
 return n;
}

void buildList(LNode **headRef){
 int i;
 for(i=7;i>0;i--){
  LNode *n = newNode(i);
  n->next = *headRef;
  *headRef = n;
 }
}

void freeMem(LNode *head){
    LNode *temp;
    while(head != NULL){
        temp = head;
        head = head->next;
        free(temp);
    }
}

void display(LNode *head){
 while(head->next != NULL){
  printf("%d->",head->data);
  head = head->next;
 }
 printf("%d\n",head->data);
}


LNode* buildBST(LNode* head){
        if(head == NULL || head->next == NULL) return head;
        LNode *root = NULL;
        LNode *slow = head;
        LNode *fast = head;
        LNode *prev = NULL;
        while(fast != NULL && fast->next != NULL){
                prev = slow;
                slow = slow->next;
                fast = fast->next->next;
        }

        root = slow;
        prev->next = NULL;
        root->left = buildBST(head);
        root->next = buildBST(slow->next);
        return root;
}

void preorder(LNode* root){
 if(root != NULL){
  printf("%d ",root->data);
  preorder(root->left);
  preorder(root->next);
 }
}

void inorder(LNode* root){
 if(root != NULL){
  inorder(root->left);
  printf("%d ",root->data);
  inorder(root->next);
 }
}

void postorder(LNode* root){
 if(root != NULL){
  postorder(root->left);
  postorder(root->next);
  printf("%d ",root->data);
 }
}

int main(){
 LNode *head = NULL;
 LNode *root = NULL;
 buildList(&head);
 display(head);
 root = buildBST(head);
 preorder(root);
 printf("\n");
 inorder(root);
 printf("\n");
 postorder(root);
// freeMem(head);
 return 0;
}

No comments:

Post a Comment