it is easy to traverse the array. as u can directly reach middle element in constant time. but for linked list u cant do dat. so the time complexity of both the solution given above are O(nlogn). is there any other better complexity solution.
On 3 May 2010 17:41, jalaj jaiswal <[email protected]> wrote: > for simplicity in writin algo i've taken sorted array instead of list > struct node * create( int *sorted,number of elements){ > struct node *temp,*left,*right; > int tempii[100],tempiii[100]; > if(number of elemnts ==0) > return NULL; > temp->data=sorted[mid]; > temp->left=NULL; > temp->right=NULL; > if number of elements == 1 > return temp; > int count=0; > for(int i=0;i<mid;i++){ > tempii[i]=sorted[i]; > count++; > } > left=create(int *tempii,count); > temp->left=left; > count=0; > for(i=mid+1;i<numberofelemnts;i++){ > tempiii[i]=sorted[i]; > count++; > } > right=create(int *tempiii,count); > temp->right=right; > > return temp; > > } > > On Mon, May 3, 2010 at 5:36 PM, Rohit Saraf > <[email protected]>wrote: > >> 1) Make the middle element the root. >> Recursively make the left and right subtrees from the left and right >> halves of the link list. >> >> 2) Implement balanced insertion in trees (via rotations on every step...). >> Now insert each element >> -------------------------------------------------- >> Rohit Saraf >> Second Year Undergraduate, >> Dept. of Computer Science and Engineering >> IIT Bombay >> http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> >> >> >> >> On Sun, May 2, 2010 at 6:38 PM, divya <[email protected]> wrote: >> >>> u are given a sorted lnked list construct a balanced binary search >>> tree from it. >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To post to this group, send email to [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]<algogeeks%[email protected]> >>> . >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >>> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]<algogeeks%[email protected]> >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > > > -- > With Regards, > Jalaj Jaiswal > +919026283397 > B.TECH IT > IIIT ALLAHABAD > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
