PreOrder and PostOrder traversal by modifying morris traversal

morris traversal postorder
morris traversal preorder
morris traversal animation
morris traversal wiki
preorder traversal
postorder traversal without recursion
preorder traversal iterative
postorder traversal without recursion and stack

The morris traversal works great for InOrder traversal with O(n) time and O(1) space. Is it possible to just by changing a few things achieve PreOrder and PostOrder traversal using the same algorithm.

I dont think we can Implement post order using threads . In post order we have to traverse both the children then their parent. We can establish a link from child to parent, but after that we cant go up this parent coz their are no links.(one points to left child and one to its right child none pointing upwards)

             1
            / \
           2   3
          / \
         4   5

we can create a thread at 4's right node pointing to node 5 . We can create a thread at 5's right node pointing to node 2 .

But at node 2 there are no empty pointers to create any threads. Node 2 already has its pointers pointing to node 4 & 5.

binary tree, morris traversal works great for InOrder traversal with O(n) time and O(1) space . Is it possible to just by changing a few things achieve PreOrder and PostOrder� Postorder traversal of Binary Tree without recursion and without stack; Postorder predecessor of a Node in Binary Search Tree; Find n-th node in Postorder traversal of a Binary Tree; Check if a binary tree is subtree of another binary tree using preorder traversal : Iterative; Find parent of given node in a Binary Tree with given postorder

I know the solution for Preorder using morison Algo.

here is the java Code

public static void morisonPreOrder(TreeNode root) {
    TreeNode curr = root, tmp=null;

    while (curr != null) {
        if(curr.leftNode == null) {
            System.out.print(curr.value + "  ");
            curr = curr.rightNode;
        } else {
            tmp = curr.leftNode;
            while (tmp.rightNode != null && tmp.rightNode != curr) {
                tmp = tmp.rightNode;
            }

            if(tmp.rightNode == null) {
                System.out.print(curr.value + "  ");
                tmp.rightNode = curr;
                curr = curr.leftNode;
            } else {
                tmp.rightNode = null;
                curr = curr.rightNode;
            }
        }
    }
}

Morris traversal for Preorder, Using Morris Traversal, we can traverse the tree without using stack and recursion. The algorithm for Preorder is almost similar to Morris traversal for Inorder. 1. Morris traversal modifies the tree during the process. preorder traversal � Print Postorder traversal from given Inorder and Preorder traversals� 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.

Post-order can be achieved by simply reversing the in-order Morris algorithm. To explain,

In-order python Morris implementation:

def in_order(root):
    if not root:
        return []
    current = root
    in_order_list = []
    while current:
        if not current.left:
            in_order_list += [current.val] # Mark current as visited
            current = current.right
        else:
            # find the right most of the left tree
            predecessor = current.left
            while (predecessor.right) and (predecessor.right != current):
                predecessor = predecessor.right
            # and create a link from this to current
            if not predecessor.right:
                predecessor.right = current
                current = current.left
            else: # now bring back the tree to it's original shape
                 predecessor.right = None
                 in_order_list += [current.val]
                 current = current.right
    return in_order

For post-order, begin with current and if current.right is empty - start looking towards left. If not, find left most predecessor and link the left of this predecessor back to current. (In short, flip the lefts in in-order to rights and keep inserting nodes to the beginning of the visited list ;) )

Post-order Python Morris

def post_order(root):
    if not root:
        return []
    current = root
    post_order_list = []
    while current:
        if not current.right:
            post_order_list.insert(0, current.val)
            current = current.left
        else:
            # find left most of the right sub-tree
            predecessor = current.right
            while (predecessor.left) and (predecessor.left != current):
                predecessor = predecessor.left
            # and create a link from this to current
            if not predecessor.left:
                post_order_list.insert(0, current.val)
                predecessor.left = current
                current = current.right
            else:
                predecessor.left = None
                current = current.left
    return post_order

Tree traversal, In computer science, tree traversal is a form of graph traversal and refers to the process of The pre-order traversal is a topologically sorted one, because a parent node is processed Given a tree with distinct elements, either pre-order or post-order paired with in-order is Morris in-order traversal using threading[ edit]. For learning morris postorder tree traversal first we should know about what is postorder tree traversal. Postorder Tree Traversal: It is a type of tree traversal in which first we visit Left subtree then Right Subtree and then the root of the graph. Steps of Morris Postorder Tree Traversal algorithm: 1. Make input tree left subtree of temp. 2

Here is the sample code for pre order traversal using modified morris traversal.

You can use in a similar way to modify the right predecessor's left link for post order traversal.

I didn't get time to test the code. Please let me know if something is wrong in this code.

void preOrderNonRecursive( BSTNode* root )
{
    if(!root)
        return;
    BSTNode* cur = root;

    while(cur)
    {
        bool b = false;
        BSTNode* pre = NULL;
        if (cur->left)
        {
            pre = cur->left;
            while(pre->right && pre->right != cur)
                pre = pre->right;
            if(!pre->right)
            {
                pre->right = cur;
                b = true;
            }               
            else
                pre->right = NULL;
        }   
        else
            printf("%d\n",cur->val);

        if(b)
        {   
            printf("%d\n",cur->val);
            cur = cur->left;        
        }
        else            
            cur = cur->right;
    }
}

Morris Traversal-Time O(n), Space O(1), inorder, preorder, postorder , Preorder, basically the same, just one line of change. def preorderTraversal(self, root): result=[] node=root while node!=None: #print(node.val) if� Mix Order Traversal is a tree traversal technique, which involves any two of the existing traversal techniques like Inorder, Preorder and Postorder Traversal. Any two of them can be performed or alternate levels of given tree and a mix traversal can be obtained.

/PreOrder Implementation Without stack and recursion/

private static void morrisPreorder(){
        while(node != null){
            System.out.println(node.getData());
            if (node.getLeftNode() == null){
                node = node.getRightNode();
            } else {
                Node rightnode = node.getRightNode();
                Node current = node.getLeftNode();
                while(current.getRightNode() != null && current.getRightNode().getData() != node.getData())
                    current = current.getRightNode();
                if(current.getRightNode() == null){
                    current.setRightNode(node.getRightNode());
                    node = node.getLeftNode();
                } else {
                    node = node.getRightNode();
                }
            }
        }
    }

C++ Iterative, Recursive and Morris Traversal, Last Edit: September 28, 2018 2:52 AM Morris tree traversal of "reversed" preorder (means, travel right child before left child), and add data to the beginning of� Ch-4.2:Tree Traversal(Inorder ,Preorder ,Postorder) ,leftMostChild-rightSibling representation In this Lecture i covered Tree Traversal(Preorder , Inorder ,

Tree Traversal (preorder / postorder) – Jun Zhang, Given a binary tree, return the preorder traversal of its nodes' values. Morris Traversal is an interesting tree traversal algorithm which is presented by The only thing we need change is the order of the sub tree traversal. Given a binary tree. Modify it in such a way that after modification you can have a preorder traversal of it using only the right pointers. During modification, you can use right as well as left pointers.

Loop-free algorithms for traversing binary trees, modified to yield loop-free sinole-visit traversal algorithms in "non-standard" orders. traversal is loop-free but preorder, inorder and postorder traversal are not, the J. M. Morris, Traversing binary trees simply and cheaply, Information� A naive method is to first construct the tree, then use simple recursive method to print postorder traversal of the constructed tree. We can print postorder traversal without constructing the tree. The idea is, root is always the first item in preorder traversal and it must be the last item in postorder traversal.

Iterative traversals for Binary Trees, Here we will attempt to develop iterative traversals, without modifying the structure. Preorder(Tree *p) { stack < Tree* > S; do { while (p!=NULL) { // storea� Pre-order traversal can be used to make a prefix expression (Polish notation) from expression trees: traverse the expression tree pre-orderly. For example, traversing the depicted arithmetic expression in pre-order yields "+ * A - B C + D E". Post-order traversal can generate a postfix representation (Reverse Polish notation) of a binary

Comments
  • looks like the above code is for inorder-traversal, not for pre-order