I could not understand why people are using extra space. And you would be able to change the actual structure of the tree. How horrible is the idea and people are still supporting it !!!! Goodness me. The signature of the function will be :
tree* inordersucc(tree *root,tree *node); UTKARSH SRIVASTAV's idea is the best idea. On 6 August 2011 20:36, saurabh singh <[email protected]> wrote: > @deepankar cool idea...:) > @sagar sol 1 is better,What if we are simply passed a tree in which we have > to search... > > On Sat, Aug 6, 2011 at 8:33 PM, Dipankar Patro <[email protected]>wrote: > >> how about using the threaded binary tree? >> >> >> On 6 August 2011 20:25, sagar pareek <[email protected]> wrote: >> >>> Sorry for typo mistake in prev solution >>> >>> >>> 2 solutions >>> >>> 1. >>> >>> node* arr[100]; >>> int j=0; >>> >>> inorder(node * ptr) >>> { >>> if(ptr) >>> { >>> inorder(ptr->left); >>> arr[j++]=ptr; >>> inorder(ptr->right); >>> } >>> } >>> >>> u will have all the addresses in inorder fashion.... now its easy to >>> watch any successor ... :P :P >>> >>> 2. best solution >>> //considering that there is 1 more field in the structure >>> >>> >>> typedef struct bin >>> { >>> struct bin* left; >>> int data; >>> struct bin* right; >>> struct bin* succ; >>> } node; >>> >>> >>> >>> inorder(node* ptr) >>> { >>> if(ptr) >>> { >>> static int p=0; >>> inorder(ptr->left) >>> if(p) ptr->succ=prev; //here we are skipping 1st left most leaf >>> because it has no successor >>> p=1; >>> prev=ptr; >>> inorder(ptr->right); >>> } >>> } >>> >>> >>> simplest and short code :) :) :) >>> >>> anyone have better code??? >>> >>> On Sat, Aug 6, 2011 at 8:24 PM, sagar pareek <[email protected]>wrote: >>> >>>> 2 solutions >>>> >>>> 1. >>>> >>>> node* arr[100]; >>>> int j=0; >>>> >>>> inorder(node * ptr) >>>> { >>>> if(ptr) >>>> { >>>> inorder(ptr->left); >>>> arr[j++]=ptr; >>>> inorder(ptr->right); >>>> } >>>> } >>>> >>>> u will have all the addresses in inorder fashion.... now its easy to >>>> watch any successor ... :P :P >>>> >>>> 2. best solution >>>> //considering that there is 1 more field in the structure >>>> >>>> >>>> typedef struct bin >>>> { >>>> struct bin* left; >>>> int data; >>>> struct bin* right; >>>> struct bin* succ; >>>> } >>>> >>>> >>>> inorder >>>> { >>>> if(ptr) >>>> { >>>> static int p=0; >>>> inorder(ptr->left) >>>> if(p) ptr->succ=prev; //here we are skipping 1st left most leaf >>>> because it has no successor >>>> p=1; >>>> prev=ptr; >>>> inorder(ptr->right); >>>> } >>>> } >>>> >>>> >>>> simplest and short code :) :) :) >>>> >>>> anyone have better code??? >>>> >>>> >>>> >>>> >>>> >>>> On Sat, Aug 6, 2011 at 6:52 PM, UTKARSH SRIVASTAV < >>>> [email protected]> wrote: >>>> >>>>> sorry two cases only >>>>> >>>>> >>>>> On Sat, Aug 6, 2011 at 6:21 AM, UTKARSH SRIVASTAV < >>>>> [email protected]> wrote: >>>>> >>>>>> pseudo code >>>>>> >>>>>> three cases are possible >>>>>> 1.node has left and right child >>>>>> then inorder succesor will be leftmost child of right child >>>>>> 2. node has left child and no right child or no left and right chid >>>>>> if node is left child of it's parent then inorder succesor is >>>>>> it's parent only >>>>>> if node is right child of it's parent then keep on moving upwards >>>>>> until you find a parent which is left child of it's parent >>>>>> then it will be the inorder succesor....if you reach node then no >>>>>> inorder succesor >>>>>> >>>>>> -- >>>>>> *UTKARSH SRIVASTAV >>>>>> CSE-3 >>>>>> B-Tech 3rd Year >>>>>> @MNNIT ALLAHABAD* >>>>>> >>>>>> >>>>> >>>>> >>>>> -- >>>>> *UTKARSH SRIVASTAV >>>>> CSE-3 >>>>> B-Tech 3rd Year >>>>> @MNNIT ALLAHABAD* >>>>> >>>>> -- >>>>> 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. >>>>> >>>> >>>> >>>> >>>> -- >>>> **Regards >>>> SAGAR PAREEK >>>> COMPUTER SCIENCE AND ENGINEERING >>>> NIT ALLAHABAD >>>> >>>> >>> >>> >>> -- >>> **Regards >>> SAGAR PAREEK >>> COMPUTER SCIENCE AND ENGINEERING >>> NIT ALLAHABAD >>> >>> -- >>> 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. >>> >> >> >> >> -- >> >> ___________________________________________________________________________________________________________ >> >> Please do not print this e-mail until urgent requirement. Go Green!! >> Save Papers <=> Save Trees >> >> -- >> 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. >> > > > > -- > Saurabh Singh > B.Tech (Computer Science) > MNNIT ALLAHABAD > > > -- > 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.
