HI, I think the following solution will solve the problem. It's not as elegant as the previous one but a straight forward try.
post_order( root ) { while( root != NULL ) { if( root->left != NULL ) { push( LeftStack, root ) ; root = root->left ; } else if( root->right != NULL ) { push( RightStack, root ) ; root = root->right ; } else { print( root ) ; while( stackNotEmpty( RightStack ) ) print( pop( RightStack ) ; while( stackNotEmpty( LeftStack ) ) { root = pop( LeftStack ) ; if( root->right != NULL ) break ; print( root ) ; } if( root->right != NULL ) // break ; { push( RightStack, root ) ; root = root->right ; } else root = NULL ; } } } Correct me if I am wrong. Thanks and Regards, K.V.Chandra Kumar. On 09/09/2007, chandra kumar <[EMAIL PROTECTED]> wrote: > > Hi, > But in your second while( ) loop when the check 'root->left = NULL' > executes 'root' is already NULL, because only then the first loop > terminates. So you need to insert the following statement inbetween the > loops > > root = pop( ) > > Also your solution assumes that the value at the nodes are of 'single > character'. Say, if the values are of multiple character strings, then > instead of 'string_reverse( )' the function 'reverse_words_in_string( )'. > > Other than this the solution should be perfect. Correct me if I'm > wrong. > > Thanks and Regards, > K.V.Chandra Kumar. > > On 07/09/2007, anshu <[EMAIL PROTECTED]> wrote: > > > > > > An alternative algorithm that works without the explored() function > > could be as under. > > Just written a rough algorithm, there are a few more optimizations in > > loop possible,.. > > The basi idea used here is - > > Post order mean "Data-Left-Right" > > If pre-order algorithm be executed with the difference that instead of > > left we explore right. > > The final order obtained when reversed will give post order. > > > > > > post_order(root) > > { > > string_reverse( func(root)); > > } > > > > > > func(root) > > { > > do { > > while(root != NULL) > > { > > print(root->data); > > push(root); > > root=root->right; > > } > > while( root->left=NULL || stack ! empty) > > root=pop() > > if(root->left !=NULL) > > { > > root=root->left > > } > > > > }while( stack ! empty); > > > > } > > > > > > On Aug 28, 8:39 am, "chandra kumar" <[EMAIL PROTECTED]> > > wrote: > > > Hi, > > > Need more details about explored( Node * ) function, > > > > > > Consider the "NULL" input > > > > > > if your explored( NULL ) returns "true" then I guess that every > > thing > > > works fine, and also most of your checks could be eliminated ( code > > will > > > become simpler ) > > > if your explored( NULL ) returns "false", then the same case as in > > my > > > previous mail will result in wrong answer. > > > * if((s->left == null && s->right==null) > > > ||(explored(s->left)&&explored(s->right)) * > > > * ---as s->left == null && explored( s->right ) ( and vice > > versa > > > are not there )* > > > > > > Correct me if I'm wrong. > > > > > > Thanks and Regards, > > > K.V.Chandra Kumar. > > > > > > On 28/08/07, MD <[EMAIL PROTECTED]> wrote: > > > > > > > > > > > > > I think first s=pop() in while is not the right approach. This is an > > > > > > alternate approach where explored() checks if the node is visited or > > > > not... hence discarding that path.. and I think the following > > handles > > > > the null conditions as well.. (ex given by chandra) > > > > > > > void postOrderTraversal(Tree *root) > > > > { > > > > node * previous = null; > > > > node * s = root; > > > > push(s); > > > > > > > while( stack is not empty) > > > > { > > > > if(s->left && !explored(s->left)) //explored check if the node was > > > > previously visited > > > > {push(s->left); > > > > s=s->left} > > > > else > > > > {if(s->right && !explored(s->right)) > > > > {push(s->right); > > > > s=s->right;} > > > > } > > > > > > > if((s->left == null && s->right==null) ||(explored(s- > > > > >left)&&explored(s->right)) //last level-child or both childern are > > > > explored > > > > { s = pop(); // > > > > print(s->data); > > > > s= pop(); //POP Again....point s to next element. > > > > } > > > > }//end of while > > > > > > > } > > > > > > > On Aug 24, 6:17 am, "Phani Kumar Ch. V." <[EMAIL PROTECTED]> wrote: > > > > > Hi all, > > > > > > > > Please let me know if this pseudo code gives correct solution for > > > > iterative > > > > > post-order traversal of a binary tree. > > > > > ---------------------------------------------------- > > > > > void postOrderTraversal(Tree *root) > > > > > { > > > > > node * previous = null; > > > > > node * s = null; > > > > > push(root); > > > > > while( stack is not empty ) > > > > > { > > > > > s = pop(); > > > > > > > > if(s->right == null and s->left == null) > > > > > { > > > > > previous = s; > > > > > process node s; > > > > > } > > > > > else > > > > > { > > > > > if( s->right == previous or s->left == previous ) > > > > > { > > > > > previous = s; > > > > > process node s; > > > > > } > > > > > else > > > > > { > > > > > push( s ); > > > > > if(s->right) { push(s->right); } > > > > > if(s->left) { push(s->left); } > > > > > } > > > > > }} > > > > > > > > ----------------------- > > > > > Regards > > > > > Phani > > > > > > > > > > > --~--~---------~--~----~------------~-------~--~----~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---