Re: [algogeeks] Inorder Iterative code for printing paths
thanx amitesh code is working fine .. i was displaying it in other way not like this , but yea it can be shown in this way too .. On Thu, Jun 28, 2012 at 1:08 PM, Amitesh Singh wrote: > and to count no. of paths, you can do this > void printPath(node *p,node *child) > { > static int iCountPath = 0; // or pass it as an argument non-const ref. > if( p && child) > { > ++iCountPath; > std::cout << "Path: " << p->data << " => " << child->data << > std::endl; > } > } > > -- > Amitesh > > > > > On Thu, Jun 28, 2012 at 11:01 AM, Amitesh Singh > wrote: > >> void printPath(node *p,node *child) >> { >> if( p && child) >> std::cout << "Path: " << p->data << " => " << child->data << >> std::endl; >> } >> >> use this before you assign 'current' to its children. >> e.g. >> >>printPath(p,p->left) >>or >>printPath(p,p->right); >> >> >> -- >> Amitesh >> >> >> >> >> On Mon, Jun 25, 2012 at 11:34 PM, Nishant Pandey < >> nishant.bits.me...@gmail.com> wrote: >> >>> >>> thiss is iterative inorder code i am using for printing all the paths >>> of the Btree . >>> >>> but i am not able to manipulate the lengths properly when its perform >>> pop up so that i >>> can print the paths properly .. >>> >>> Can any one help by modifying the changes in this code . >>> >>> >>> >>> void inorder(struct node *root) >>> { >>> stackstack_temp; >>> >>> struct node *current,*temp; >>> int path[20]; >>> int i =0 ,j=0; >>> if(!root)return ; >>> >>> current=root; >>> bool flag=false; >>> //bool ctrl=false; >>> while(!flag) >>> { >>> >>> if(current) >>> { >>> //cout> stack_temp.push(current); >>> path[i++]=current->data; >>> if(current->left == NULL && current->right == NULL) >>> { >>> for(j=0;j>> cout<>> //i--; >>> >>> } >>> >>> cout<>> current=current->left; >>> >>> } >>> else >>> { >>> if(stack_temp.empty()) >>> { >>> flag=true; >>> } >>> else >>> { >>> current=stack_temp.top(); >>> stack_temp.pop(); >>> >>> i--; >>> >>> >>> //if(current->right) >>> //cout> current=current->right; >>> if(current) >>> i++; >>> } >>> >>> } >>> >>> } >>> >>> >>> } >>> >>> >>> >>> -- >>> Cheers, >>> >>> Nishant Pandey |Specialist Tools Development | >>> npan...@google.com | >>> +91-9911258345 >>> >>> >>> -- >>> 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. >>> >> >> > -- Cheers, Nishant Pandey |Specialist Tools Development | npan...@google.com | +91-9911258345 -- 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.
Re: [algogeeks] Inorder Iterative code for printing paths
and to count no. of paths, you can do this void printPath(node *p,node *child) { static int iCountPath = 0; // or pass it as an argument non-const ref. if( p && child) { ++iCountPath; std::cout << "Path: " << p->data << " => " << child->data << std::endl; } } -- Amitesh On Thu, Jun 28, 2012 at 11:01 AM, Amitesh Singh wrote: > void printPath(node *p,node *child) > { > if( p && child) > std::cout << "Path: " << p->data << " => " << child->data << > std::endl; > } > > use this before you assign 'current' to its children. > e.g. > >printPath(p,p->left) >or >printPath(p,p->right); > > > -- > Amitesh > > > > > On Mon, Jun 25, 2012 at 11:34 PM, Nishant Pandey < > nishant.bits.me...@gmail.com> wrote: > >> >> thiss is iterative inorder code i am using for printing all the paths of >> the Btree . >> >> but i am not able to manipulate the lengths properly when its perform pop >> up so that i >> can print the paths properly .. >> >> Can any one help by modifying the changes in this code . >> >> >> >> void inorder(struct node *root) >> { >> stackstack_temp; >> >> struct node *current,*temp; >> int path[20]; >> int i =0 ,j=0; >> if(!root)return ; >> >> current=root; >> bool flag=false; >> //bool ctrl=false; >> while(!flag) >> { >> >> if(current) >> { >> //cout stack_temp.push(current); >> path[i++]=current->data; >> if(current->left == NULL && current->right == NULL) >> { >> for(j=0;j> cout<> //i--; >> >> } >> >> cout<> current=current->left; >> >> } >> else >> { >> if(stack_temp.empty()) >> { >> flag=true; >> } >> else >> { >> current=stack_temp.top(); >> stack_temp.pop(); >> >> i--; >> >> >> //if(current->right) >> //cout current=current->right; >> if(current) >> i++; >> } >> >> } >> >> } >> >> >> } >> >> >> >> -- >> Cheers, >> >> Nishant Pandey |Specialist Tools Development | >> npan...@google.com | >> +91-9911258345 >> >> >> -- >> 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.
Re: [algogeeks] Inorder Iterative code for printing paths
void printPath(node *p,node *child) { if( p && child) std::cout << "Path: " << p->data << " => " << child->data << std::endl; } use this before you assign 'current' to its children. e.g. printPath(p,p->left) or printPath(p,p->right); -- Amitesh On Mon, Jun 25, 2012 at 11:34 PM, Nishant Pandey < nishant.bits.me...@gmail.com> wrote: > > thiss is iterative inorder code i am using for printing all the paths of > the Btree . > > but i am not able to manipulate the lengths properly when its perform pop > up so that i > can print the paths properly .. > > Can any one help by modifying the changes in this code . > > > > void inorder(struct node *root) > { > stackstack_temp; > > struct node *current,*temp; > int path[20]; > int i =0 ,j=0; > if(!root)return ; > > current=root; > bool flag=false; > //bool ctrl=false; > while(!flag) > { > > if(current) > { > //cout path[i++]=current->data; > if(current->left == NULL && current->right == NULL) > { > for(j=0;j cout< //i--; > > } > > cout< current=current->left; > > } > else > { > if(stack_temp.empty()) > { > flag=true; > } > else > { > current=stack_temp.top(); > stack_temp.pop(); > > i--; > > > //if(current->right) > //coutright; > if(current) > i++; > } > > } > > } > > > } > > > > -- > Cheers, > > Nishant Pandey |Specialist Tools Development | > npan...@google.com | > +91-9911258345 > > > -- > 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.
[algogeeks] Inorder Iterative code for printing paths
thiss is iterative inorder code i am using for printing all the paths of the Btree . but i am not able to manipulate the lengths properly when its perform pop up so that i can print the paths properly .. Can any one help by modifying the changes in this code . void inorder(struct node *root) { stackstack_temp; struct node *current,*temp; int path[20]; int i =0 ,j=0; if(!root)return ; current=root; bool flag=false; //bool ctrl=false; while(!flag) { if(current) { //coutleft == NULL && current->right == NULL) { for(j=0;jleft; } else { if(stack_temp.empty()) { flag=true; } else { current=stack_temp.top(); stack_temp.pop(); i--; //if(current->right) //cout
Re: [algogeeks] inorder predecessor
is it not possible to traverse tree in order and store in array. then figure out the element and print the previous element? On Fri, Aug 26, 2011 at 2:04 PM, Vikram Singh wrote: > i figured out algo to find the inorder predecessor of a bst without > using parent pointer... just wanna confirm if its missing any case > > if the left child(subtree) of node exist, then predecessor ll be the > max value in the left subtree. > > else predecessor ll be one of the ancestor in this case, starting > from the given node, we hv to find a closest ancestrous node which is > right child of its parent... the parent ll be the predecessor... > > and i made the parent implementation without changing the structure of > the node... using while loop... > > let me know if i m missing ant case... > > -- > 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.
[algogeeks] inorder predecessor
i figured out algo to find the inorder predecessor of a bst without using parent pointer... just wanna confirm if its missing any case if the left child(subtree) of node exist, then predecessor ll be the max value in the left subtree. else predecessor ll be one of the ancestor in this case, starting from the given node, we hv to find a closest ancestrous node which is right child of its parent... the parent ll be the predecessor... and i made the parent implementation without changing the structure of the node... using while loop... let me know if i m missing ant case... -- 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.
Re: [algogeeks] inorder
My both the ideas are not for any particular node On Sat, Aug 6, 2011 at 8:45 PM, payel roy wrote: > 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 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 wrote: >> >>> how about using the threaded binary tree? >>> >>> >>> On 6 August 2011 20:25, sagar pareek 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 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 < > usrivastav...@gmail.com> wrote: > >> sorry two cases only >> >> >> On Sat, Aug 6, 2011 at 6:21 AM, UTKARSH SRIVASTAV < >> usrivastav...@gmail.com> 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 succesorif 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 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. >> > > > > -- > **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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] inorder
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 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 wrote: > >> how about using the threaded binary tree? >> >> >> On 6 August 2011 20:25, sagar pareek 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 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 < usrivastav...@gmail.com> wrote: > sorry two cases only > > > On Sat, Aug 6, 2011 at 6:21 AM, UTKARSH SRIVASTAV < > usrivastav...@gmail.com> 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 succesorif 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 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. > -- **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 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. >>> >> >> >> >> -- >> >> ___ >> >> Please do not print this e-mail until urgent requirement. Go Green!! >> Save Papers <=> Save T
Re: [algogeeks] inorder
@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 wrote: > how about using the threaded binary tree? > > > On 6 August 2011 20:25, sagar pareek 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 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 < >>> usrivastav...@gmail.com> wrote: >>> sorry two cases only On Sat, Aug 6, 2011 at 6:21 AM, UTKARSH SRIVASTAV < usrivastav...@gmail.com> 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 succesorif 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 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. >>> >>> >>> >>> -- >>> **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 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. >> > > > > -- > > ___ > > 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 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. > -- 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 algogeeks@googlegr
Re: [algogeeks] inorder
how about using the threaded binary tree? On 6 August 2011 20:25, sagar pareek 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 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 < >> usrivastav...@gmail.com> wrote: >> >>> sorry two cases only >>> >>> >>> On Sat, Aug 6, 2011 at 6:21 AM, UTKARSH SRIVASTAV < >>> usrivastav...@gmail.com> 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 succesorif 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 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. >>> >> >> >> >> -- >> **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 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. > -- ___ 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 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.
Re: [algogeeks] inorder
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 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 > wrote: > >> sorry two cases only >> >> >> On Sat, Aug 6, 2011 at 6:21 AM, UTKARSH SRIVASTAV < >> usrivastav...@gmail.com> 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 succesorif 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 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. >> > > > > -- > **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 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.
Re: [algogeeks] inorder
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 wrote: > sorry two cases only > > > On Sat, Aug 6, 2011 at 6:21 AM, UTKARSH SRIVASTAV > 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 succesorif 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 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. > -- **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 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.
Re: [algogeeks] inorder
sorry two cases only On Sat, Aug 6, 2011 at 6:21 AM, UTKARSH SRIVASTAV 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 succesorif 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 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.
Re: [algogeeks] inorder
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 succesorif you reach node then no inorder succesor -- *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 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.
Re: [algogeeks] inorder
@harshit can you provide a running code and prove how its running complexity is better than the complexity of my code On Sat, Aug 6, 2011 at 6:44 PM, harshit sethi wrote: > inordersucc(struct tree* p) > { > if(p->right !=NULL) > return p->right; > > struct tree* ptr,*psuc; > ptr=root; > > while(ptr->info!=x->info) > { > > if(x->infoinfo) > { > psuc=ptr; > ptr=ptr->left; > } > > else > ptr=ptr->right; > } > > > return psuc; > } > > On 8/6/11, Anuj Kumar wrote: > > i am sending the running code :) > > > > #include > > > > using namespace std; > > struct node > > { > > int data; > > struct node *lc,*rc; > > node(int d) > > { > > data=d;lc=rc=NULL; > > } > > }; > > int ret,fl; > > void inorder(struct node *root,int d) > > { > > if(ret==1)return; > > if(root==NULL)return; > > inorder(root->lc,d); if(ret==1)return; > > if(fl==1){cout > if(root->data==d){fl=1;} > > inorder(root->rc,d); if(ret==1)return; > > } > > int main() > > { > > struct node *root=new node(2); > > root->lc=new node(1); > > root->rc=new node(3); > > root->rc->rc=new node(6); > > ret=0;fl=0; > > inorder(root,3); > > return 0; > > } > > > > On Sat, Aug 6, 2011 at 5:50 PM, Aman Goyal > wrote: > > > >> .. pseudo code for finding inorder successor of a node without parent > >> field.. > >> > >> -- > >> 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. > >> > > > > > > > > -- > > Anuj Kumar > > Third Year Undergraduate, > > Dept. of Computer Science and Engineering > > NIT Durgapur > > > > -- > > 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. > > -- Anuj Kumar Third Year Undergraduate, Dept. of Computer Science and Engineering NIT Durgapur -- 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.
Re: [algogeeks] inorder
inordersucc(struct tree* p) { if(p->right !=NULL) return p->right; struct tree* ptr,*psuc; ptr=root; while(ptr->info!=x->info) { if(x->infoinfo) { psuc=ptr; ptr=ptr->left; } else ptr=ptr->right; } return psuc; } On 8/6/11, Anuj Kumar wrote: > i am sending the running code :) > > #include > > using namespace std; > struct node > { > int data; > struct node *lc,*rc; > node(int d) > { > data=d;lc=rc=NULL; > } > }; > int ret,fl; > void inorder(struct node *root,int d) > { > if(ret==1)return; > if(root==NULL)return; > inorder(root->lc,d); if(ret==1)return; > if(fl==1){cout if(root->data==d){fl=1;} > inorder(root->rc,d); if(ret==1)return; > } > int main() > { > struct node *root=new node(2); > root->lc=new node(1); > root->rc=new node(3); > root->rc->rc=new node(6); > ret=0;fl=0; > inorder(root,3); > return 0; > } > > On Sat, Aug 6, 2011 at 5:50 PM, Aman Goyal wrote: > >> .. pseudo code for finding inorder successor of a node without parent >> field.. >> >> -- >> 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. >> > > > > -- > Anuj Kumar > Third Year Undergraduate, > Dept. of Computer Science and Engineering > NIT Durgapur > > -- > 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.
Re: [algogeeks] inorder
i am sending the running code :) #include using namespace std; struct node { int data; struct node *lc,*rc; node(int d) { data=d;lc=rc=NULL; } }; int ret,fl; void inorder(struct node *root,int d) { if(ret==1)return; if(root==NULL)return; inorder(root->lc,d); if(ret==1)return; if(fl==1){coutdata==d){fl=1;} inorder(root->rc,d); if(ret==1)return; } int main() { struct node *root=new node(2); root->lc=new node(1); root->rc=new node(3); root->rc->rc=new node(6); ret=0;fl=0; inorder(root,3); return 0; } On Sat, Aug 6, 2011 at 5:50 PM, Aman Goyal wrote: > .. pseudo code for finding inorder successor of a node without parent > field.. > > -- > 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. > -- Anuj Kumar Third Year Undergraduate, Dept. of Computer Science and Engineering NIT Durgapur -- 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.
[algogeeks] inorder
.. pseudo code for finding inorder successor of a node without parent field.. -- 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.
Re: [algogeeks] Inorder traversal on binary tree
Hi, On Sat, Nov 28, 2009 at 1:53 PM, Nayn wrote: > Hi, > > We have to find inorder traversal on a binary tree whose leaf nodes > are connected in a singly circular linked list. The tree might not be > a complete binary tree. > >I don't think the presence of the linked list would change how inorder traversal is done. The presence of the linked list is to facilitate easy retrieval of consecutive blocks in the file system (in the context of B+ tree), if I remember correctly. Regards Aditya Shankar Thanks > Nayn > > -- > > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@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 algoge...@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.
Re: [algogeeks] Inorder traversal on binary tree
Read about B+ trees. It might help. On Sat, Nov 28, 2009 at 1:53 PM, Nayn wrote: > Hi, > > We have to find inorder traversal on a binary tree whose leaf nodes > are connected in a singly circular linked list. The tree might not be > a complete binary tree. > > Thanks > Nayn > > -- > > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@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. > > > -- Shishir Mittal Ph: +91 9936 180 121 -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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.
[algogeeks] Inorder traversal on binary tree
Hi, We have to find inorder traversal on a binary tree whose leaf nodes are connected in a singly circular linked list. The tree might not be a complete binary tree. Thanks Nayn -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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.
[algogeeks] inorder sucessor and predecessor
Hello everyone I am new to this group and i am not of CS origin. So can you people help me out in finding the soln for inorder sucessor and predecessor. Actuall i know the logic, but i am not able to write an algorithm for it. I searched for the algo in this grps, but cudnt get it. So can anyone help me by provifing the algorithm. Thanks Karthi