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

A simpler approach would be to do the symmetrically opposite of preorder morris traversal and print the nodes in the reverse order.

    TreeNode* node = root;
    stack<int> s;
    while(node) {
        if(!node->right) {
            s.push(node->val);
            node = node->left;
        }
        else {
            TreeNode* prev = node->right;

            while(prev->left && prev->left != node)
                prev = prev->left;

            if(!prev->left) {
                prev->left = node;
                s.push(node->val);
                node = node->right;
            }
            else {  
                node = node->left;
                prev->left = NULL;
            }
        }
    }

    while(!s.empty()) {
        cout << s.top() << " ";
        s.pop();
    }

    cout << endl;

Answer 2

It seems simple once you understand the concept behind it.

Basically, we are using the In-order Traversal (L-N-R) to print the post-order traversal (L-R-N) of the given Binary Tree. All we need to do is reverse the second and third part of the inorder traversal i.e. print it in the fashion L-R-N.

When a node is visited again with the help of the thread that we created earlier during the thread creation phase, It means that we are done traversing the left subtree. Hence we need to print all the left subtree nodes. So, we print the left sub nodes of the current node and left subtree nodes of the right child.

After this step, we've printed all the left nodes, now all we need to do is print the reverse order of the right pointer. If we consider it as a simple singly linked list where the next pointer is the right child of every node in the right subtree.

Print the list in the reverse order till the current node. Go to the In-order successor node which you saved and follow the same.

I hope It makes things a bit clearer for you.

PS: Linked list reversal is used to reverse the second and third part of the inorder traversal.

Answer 3

My Java solution - it has a lot of code comments, but comment to me here if you want anything explained more.

public static void postOrder(Node root) {
    // ensures all descendants of root that are right-children
    //  (arrived at only by "recurring to right") get inner-threaded
    final Node fakeNode = new Node(0);    // prefer not to give data, but construction requires it as primitive
    fakeNode.left = root;

    Node curOuter = fakeNode;
    while(curOuter != null){    // in addition to termination condition, also prevents fakeNode printing
        if(curOuter.left != null){
            final Node curOuterLeft = curOuter.left;

            // Find in-order predecessor of curOuter
            Node curOuterInOrderPred = curOuterLeft;
            while(curOuterInOrderPred.right != null && curOuterInOrderPred.right != curOuter){
                curOuterInOrderPred = curOuterInOrderPred.right;
            }

            if(curOuterInOrderPred.right == null){
                // [Outer-] Thread curOuterInOrderPred to curOuter
                curOuterInOrderPred.right = curOuter;

                // "Recur" on left
                curOuter = curOuterLeft;

            } else {    // curOuterInOrderPred already [outer-] threaded to curOuter
                        //  -> [coincidentally] therefore curOuterLeft's left subtree is done processing
                // Prep for [inner] threading (which hasn't ever been done yet here)...
                Node curInner = curOuterLeft;
                Node curInnerNext = curInner.right;
                // [Inner-] Thread curOuterLeft [immediately backwards] to curOuter [its parent]
                curOuterLeft.right = curOuter;
                // [Inner-] Thread the same [immediately backwards] for all curLeft descendants
                //  that are right-children (arrived at only by "recurring" to right)
                while(curInnerNext != curOuter){
                    // Advance [inner] Node refs down 1 level (to the right)
                    final Node backThreadPrev = curInner;
                    curInner = curInnerNext;
                    curInnerNext = curInnerNext.right;
                    // Thread immediately backwards
                    curInner.right = backThreadPrev;
                }

                // curInner, and all of its ancestors up to curOuterLeft,
                //  are now indeed back-threaded to each's parent
                // Print them in that order until curOuter
                while(curInner != curOuter){
                    /*
                        -> VISIT
                     */
                    System.out.print(curInner.data + " ");

                    // Move up one level
                    curInner = curInner.right;
                }

                // "Recur" on right
                curOuter = curOuter.right;
            }

        } else {
            // "Recur" on right
            curOuter = curOuter.right;
        }
    }
}

class Node {
  Node left;
  Node right;
  int data;

  Node(int data) {
      this.data = data;
      left = null;
      right = null;
  }
}

Answer 4

Morris Traversal T(n) = O(n) S(n) = O(1)

Video link - https://www.youtube.com/watch?v=80Zug6D1_r4

Question link - https://leetcode.com/problems/binary-tree-postorder-traversal/

We will modify the preorder Morris traversal from root->left->right to root->right->left. For this we need to do one more change. While in normal preorder and inorder, we were creating thread from right most node of left subtree to present node, here we will create thread from left most node of right subtree to present node as here we have to cover right subtree before left subtree

        class Solution {
        public:
        vector<int> postorderTraversal(TreeNode* root) {
            vector<int> ans;
            while(root)
            {
                TreeNode *curr = root;//We will create thread from left most node of right subtree to present node and will travell to that node using curr
                                        
                if(curr->right)//if root has right child
                            //We can't push directly this root node val to ans as we are not sure whether we are here
                            //thorough thread link after covering right subtree or we are here for the first time
                {
                    curr = curr->right;
                    while(curr->left && curr->left != root)//go to left most node of right subtree
                        curr=curr->left;
                    if(curr->left != root)//not threaded yet
                    {
                        ans.push_back(root->val);//it means root was visited for first time and this is modified preorder hence 
                                                //push this node's val to ans
                        curr->left = root;//create the thread
                        root = root->right;//go to right to cover right subtree as modified preorder is root->right->left
                    }
                    else//was threaded
                    {
                        curr->left = NULL;//break the thread
                        root = root->left;//right subtree has been covered hence now cover the left one
                                            //no need to push this node value as we are here for the second time using thread
                                            //link
                    }
                }
                else//root hasn't right child
                {
                    ans.push_back(root->val);//modified preorder is root->right->left hence push this value before going to left
                    root = root->left;
                }
            }
            reverse(ans.begin(),ans.end());//reversing root->right->left to left->right->root to make it post order
            return ans;
        }
    }; 

Answer 5

While I was working on a problem in leetcode which required morris tree traversal came across this Chinese blog which explained it very precise. This is the same idea as the accepted answer.

But I'm unable to wrap my head around the space complexity of post order morris tree traversal. Can it's complexity be be O(1) ? or is it not possible ? Can anybody clarify about that ?