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, middle–1);
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