@rahul : Here are the boundary cases need to be taken care of :- suppose given BST is the following :-
root=allocate(70); root->right=allocate(75); root->left=allocate(50); root->left->left=allocate(20); root->left->left->right=allocate(25); root->left->left->left=allocate(10); root->left->right=allocate(60); root->left->right->right=allocate(65); root->left->right->left=allocate(55); now suppose node(20) and node(10) get swapped inorder of given tree is :- 20 10 25 50 55 60 65 70 75 now first violation is at node(20) but you wont get second voilation...because rest is in inc order. yes , it can be done by taking care of root of that first violation. On 9/3/12, Rahul Kumar Patle <patlerahulku...@gmail.com> wrote: > @bharat: +1 > i have tried some test cases.. working finely.. @anyone pls verify?? > > On Mon, Sep 3, 2012 at 11:58 AM, bharat b > <bagana.bharatku...@gmail.com>wrote: > >> while doing in-order traversal, we have to check if(prev > current) --> >> then mark prev element for swapping in the first time violation.. >> if it happens for the second time..then mark current element for >> swapping. >> swap both .. >> >> If we don't get the violation for the second time .. means both are >> side-by-side elements .. swap them .. >> >> Hope works .. If I miss any case .. correct me >> thanks, >> >> >> On Sun, Sep 2, 2012 at 7:45 PM, Rahul Kumar Patle < >> patlerahulku...@gmail.com> wrote: >> >>> @navin: can u explain ur algorithms in words pls.. >>> >>> On Sun, Sep 2, 2012 at 5:53 PM, Navin Kumar >>> <algorithm.i...@gmail.com>wrote: >>> >>>> void correctBST(struct node *root) >>>> { >>>> int flag =0; >>>> static struct node *temp1, *temp2, *temp3, *prev; >>>> static int found; >>>> >>>> if(found) return; >>>> >>>> if(root) { >>>> correctBST(root->left); >>>> if(!temp1 && prev && root->data < prev->data) { >>>> temp1 = prev; >>>> temp2 = root; >>>> swap(&(temp1->data), &(temp2->data)); >>>> flag = 1; >>>> prev = temp1; >>>> } >>>> else if(!temp3 && prev && root->data < prev->data) { >>>> temp3 = root; >>>> swap(&(temp1->data), &(temp2->data)); >>>> swap(&(temp1->data), &(temp3->data)); >>>> found = 1; >>>> return; >>>> } >>>> if(!flag) >>>> prev = root; >>>> correctBST(root->right); >>>> } >>>> } >>>> >>>> On Sun, Sep 2, 2012 at 4:02 PM, Rahul Kumar Patle < >>>> patlerahulku...@gmail.com> wrote: >>>> >>>>> help to solve the following.. >>>>> Question: Two of the nodes of a BST are swapped. Correct the BST >>>>> (taken >>>>> from GeekforGeeks <http://www.geeksforgeeks.org/archives/23272> 2nd >>>>> online test 3rd question) >>>>> >>>>> >>>>> >>>>> >>>>> -- >>>>> Thanks and Regards: >>>>> Rahul Kumar >>>>> Patle<http://www.linkedin.com/profile/view?id=106245716&trk=tab_pro> >>>>> M.Tech, School of Information Technology >>>>> Indian Institute of Technology, Kharagpur-721302, >>>>> India<http://www.iitkgp.ac.in/> >>>>> Mobile No: +91-8798049298, +91-9424738542 >>>>> Alternate Email: rahulkumarpa...@hotmail.com >>>>> >>>>> -- >>>>> You received this message because you are subscribed to the Google >>>>> Groups "Algorithm Geeks" group. >>>>> To post to this group, send email to algogeeks@googlegroups.com. >>>>> To unsubscribe from this group, send email to >>>>> algogeeks+unsubscr...@googlegroups.com. >>>>> 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 algogeeks@googlegroups.com. >>>> To unsubscribe from this group, send email to >>>> algogeeks+unsubscr...@googlegroups.com. >>>> For more options, visit this group at >>>> http://groups.google.com/group/algogeeks?hl=en. >>>> >>> >>> >>> >>> -- >>> Thanks and Regards: >>> Rahul Kumar >>> Patle<http://www.linkedin.com/profile/view?id=106245716&trk=tab_pro> >>> M.Tech, School of Information Technology >>> Indian Institute of Technology, Kharagpur-721302, >>> India<http://www.iitkgp.ac.in/> >>> Mobile No: +91-8798049298, +91-9424738542 >>> Alternate Email: rahulkumarpa...@hotmail.com >>> >>> -- >>> You received this message because you are subscribed to the Google >>> Groups >>> "Algorithm Geeks" group. >>> To post to this group, send email to algogeeks@googlegroups.com. >>> To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com. >>> 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 algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > > > -- > Thanks and Regards: > Rahul Kumar > Patle<http://www.linkedin.com/profile/view?id=106245716&trk=tab_pro> > M.Tech, School of Information Technology > Indian Institute of Technology, Kharagpur-721302, > India<http://www.iitkgp.ac.in/> > Mobile No: +91-8798049298, +91-9424738542 > Alternate Email: rahulkumarpa...@hotmail.com > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.