i guess i missed this part of bharat post :- /* If we don't get the violation for the second time .. means both are side-by-side elements .. swap them .. */ i was saying the same.....so it will work.
On 9/4/12, atul anand <[email protected]> wrote: > @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 <[email protected]> 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 >> <[email protected]>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 < >>> [email protected]> wrote: >>> >>>> @navin: can u explain ur algorithms in words pls.. >>>> >>>> On Sun, Sep 2, 2012 at 5:53 PM, Navin Kumar >>>> <[email protected]>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 < >>>>> [email protected]> 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: [email protected] >>>>>> >>>>>> -- >>>>>> 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. >>>>>> >>>>> >>>>> -- >>>>> 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. >>>>> >>>> >>>> >>>> >>>> -- >>>> 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: [email protected] >>>> >>>> -- >>>> 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. >>>> >>> >>> -- >>> 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. >>> >> >> >> >> -- >> 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: [email protected] >> >> -- >> 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. >> >> > -- 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.
