@atul: correctly caught... here you have to notice that if u get only one violation not second violation ill the last... then sure the violation is created because of swapping of previous and current of first violation... so when you got first violation and put first marker on previous time put second marker on current... suppose and the last if you don't get the second violation then 2nd marker will the current node of first violation... as in your case when we got first violation at node prev = 20 and current = 10.. mark first point at 20 and second pointer at 10.. at the last the 2nd pointer does not get change... i have checked this with other test cases.. this case is coming only when previous and current are the consecutive nodes(parent and its direct child) and one of the node is leaf node...
On Tue, Sep 4, 2012 at 1:22 AM, atul anand <[email protected]> wrote: > 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. > > -- 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.
