Convert sorted list to balanced binary search tree (BST)

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

C++:
01 Node* buildBST(ListNode* head)
02 {
03     if(head==NULL)
04         return NULL;
05     Node* hd=new Node;
06     if(head->next==NULL){
07         hd->value=head->value;
08         hd->left=NULL;
09         hd->right=NULL;
10         return hd;
11     }
12     ListNode* tmp=head;
13     ListNode* prv=head;
14     for(ListNode* test=head;test!=NULL;prv=tmp,tmp=tmp->next){
15         test=test->next;
16         if(test==NULL)
17             break;
18         test=test->next;
19     }
20     prv->next=NULL;
21     hd->value=tmp->value;
22     hd->left=buildBST(head);
23     hd->right=buildBST(tmp->next);
24     return hd;
25 }
A better solution: Build the tree recursively using an in-order traverse.
C++:
01 Node* buildBSTbetter(ListNode*& head,int start,int end)
02 {
03     if(start>end)
04         return NULL;
05     int middle=(start+end)/2;
06     Node* left_tree=buildBSTbetter(head, start, middle1);
07     Node* hd=new Node;
08     hd->value=head->value;
09     head=head->next;
10     Node* right_tree=buildBSTbetter(head,middle+1,end);
11     hd->left=left_tree;
12     hd->right=right_tree;
13     return hd;
14 }
Advertisements
This entry was posted in Array and linked list, Recursive, Tree. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s