Morris Traversal

What is Morris Traversal?

       Morris traversal is for binary  tree without the use of recursion and stack.The link is considered as a successor and the nodes are formed from the links . It is used in the case of inorder, preorder and post order traversal.

       In the perspective of Inorder Traversal :

The Reversion is first done in the leftmost node.(left-->subtree) 2.Visit the root. 3.The Reversion is being done in the rightmost node.(right-->subtree).
```
  In the perspective of Preorder Traversal:
```
The Reversion is first done in the rightmost node.(left-->subtree) 2.Visit the root. 3.The Reversion is being done in the leftmost node.(right-->subtree).
```
 In the perspective of Preorder Traversal:
```
The Reversion is first done in the leftmost node.(left-->subtree) 2.The Reversion is being done in the rightmost node.(right-->subtree). 3.Visit the root.

Implementation of Morris Traversal in case of Inorder Traversal

ALGORITHM

            1) Consider the root as the** curr** .
            2)When the **curr** is not NULL, check whether it has a left child and print**curr** then update it to the node on the right of the **curr**.
            3)In case if there is a presence of left child ,make **curr** the right chilld of the rightmost node in **curr**'s left subtree.
             4)Update the **curr** to the left node.

Code for the Morris Traversal in case of Inorder Traversal:

In case of using Morris Traversal in inorder traversal of a binary tree there are various CPP, Python and Java codes. Here I have implemented the Python code for Morris Traversal in inorder traversal of a Binary Tree.

class Node: def init(self, data): self.data = data self.left_node = None self.right_node = None

def Morris(root):

# Set current to root of binary tree 
curr = root 

while(curr is not None): 

    if curr.left_node is None: 
        print curr.data, 
        curr = curr.right_node 
    else: 
        # Find the previous (prev) of curr 
        prev = curr.left_node 
        while(prev.right_node is not None and prev.right_node != curr): 
            prev = prev.right_node 

        # Make curr as right child of its prev 
        if(prev.right_node is None): 
            prev.right_node = curr 
            curr = curr.left_node 

        # fix the right child of prev
        else: 
            prev.right_node = None
            print curr.data, 
            curr = curr.right_node 
 end

end

root = Node(4) root.left_node = Node(2) root.right_node = Node(5) root.left_node.left_node = Node(1) root.left_node.right_node = Node(3)

Morris(root)

print(data,root)

For the other form of traversal is repeated in the same pattern but in different steps.