Can we use Morris traversal for postorder?

Question

I have visited many websites but couldnt find any algorithm for Morris postOrder traversal. I know that we can use Morris algorithm for preOrder and inOrder.It will be of great help if someone points me to the postOrder Morris algorithm, if it exists.

Answer 1

I'll try to explain, how we can achieve post-order traversal using Morris method. Pre-requirement : Before explaining, post-order traversal, lets revise in-order traversal.

In In-order traversal, start from root node 1. if current node has left child then find its in-order predecessor and make root as right child of it and move left of root. [ to find predecessor, find the max element in its left subtree ] 2. if current node don't have left child , then print data and move right.

Restore Tree: The main thing which should be observe is that while performing step 1, we'll reach a point where predecessor right child is itself current node, this only happen when whole left child turned off and we start printing data from there. [ when you found no left child of current node] So for this case, we need to cut right child off of that node.

void MorriesInorder(BTnode root) { if(root == null ) return;  BTnode temp; while ( root!=null){    //case 2: when left child does not exist       if ( root.left == null ) {                 print( root.data );                root = root.right;     }else {             //find predecessor               temp = root.left;               while ( temp.right!=null &&                        temp.right!=root) //  to check restore case                    temp = temp.right;               if ( temp.right == null ) //predecessor found, converting             {                        temp.right = root;                        root = root.left;              } else {                   print root.data;                   temp.right = null; //  cut right child off                   root = root.right;               }     }  }} 

So now back to Original Question, How do we perform Postorder traversal. We'll use above concept with minor changes to achieve postorder traversal. First lets have a dummy node and make whole tree as left child of dummy node and make right child empty. [ why? Bec if we assume there is no right child of root then prinitng left child and then root become postorder traversal, Right ;) ] Now what next? Are we finished, No... only performing inorder on new tree does not make any sense, it still printing inorder traversal of original tree followed by dummy node.

First remove printing data from case 2 [ discussed in inorder traversal]

Critical Part: Now closely observe inner else block, this the piece of code which require attention. Since this temporarily extended tree is the subject of traversal as in in-order traversal except that in the inner else clause, after finding a temporary parent, nodes between p.left (included) and p (excluded) extended to the right in a modified tree are processed in the reverse order. To process them in constant time, the chain of nodes is scanned down and right references are reversed to refer to parents of nodes. Then the same chain is scanned upward, each node is visited, and the right references are restored to their original setting.

//This is Post Order :children before node( L ,R , N) void morrisPostorderTraversal(Node *root){  // Making our tree left subtree of a dummy Node Node *dummyRoot = new Node(0); dummyRoot->left = root;  //Think of P as the current node  Node *p = dummyRoot, *pred, *first, *middle, *last; while(p!=NULL){              if(p->left == NULL){         p = p->right;     } else{         /* p has a left child => it also has a predeccessor            make p as right child predeccessor of p             */         pred = p->left;         while(pred->right!=NULL && pred->right != p){             pred = pred->right;         }          if(pred->right == NULL){               // predeccessor found for first time             // modify the tree              pred->right = p;                 p = p->left;          }else {                                       // predeccessor found second time            // reverse the right references in chain from pred to p             first = p;             middle = p->left;                           while(middle!=p){                             last = middle->right;                 middle->right = first;                 first = middle;                 middle = last;             }              // visit the nodes from pred to p             // again reverse the right references from pred to p                 first = p;             middle = pred;             while(middle!=p){                  cout<<" "<<middle->data;                   last = middle->right;                           middle->right = first;                 first = middle;                 middle = last;             }              // remove the pred to node reference to restore the tree structure             pred->right = NULL;                 p = p-> right;         }     } }     }