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.
