Is it required only to retain the BST property ?? or to retain the original BST (tree)
*Shashi Kant * ***"Think positive and find fuel in failure"* http://thinkndoawesome.blogspot.com/ *System/Software Engineer* *Hewlett-Packard India Software Operations. * On Tue, Sep 4, 2012 at 1:56 PM, Rahul Kumar Patle <[email protected] > wrote: > @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. > -- 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.
