Inorder Tree Traversal – Morris Traversal

# Python program to do inorder traversal without recursion and 
# without stack Morris inOrder Traversal
# A binary tree node
class Node:
    # Constructor to create a new node
    def __init__(self, data): = data 
        self.left = None
        self.right = None
# Iterative function for inorder tree traversal
def MorrisTraversal(root):
    # Set current to root of binary tree
    current = root 
    while(current is not None):
        if current.left is None:
            print ,
            current = current.right
            #Find the inorder predecessor of current
            pre = current.left
            while(pre.right is not None and pre.right != current):
                pre = pre.right
            # Make current as right child of its inorder predecessor
            if(pre.right is None):
                pre.right = current
                current = current.left
            # Revert the changes made in if part to restore the 
            # original tree i.e., fix the right child of predecssor
                pre.right = None
                print ,
                current = current.right
# Driver program to test above function
Constructed binary tree is
          /   \
        2      3
      /  \
    4     5
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
# This code is contributed by Naveen Aili


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s