Inorder Tree Traversal without recursion and without stack ! | A binary tree node ; Generator function for iterative inorder tree traversal ; Find the inorder predecessor of current ; Make current as right child of its inorder predecessor ; Revert the changes made in the ' if ' part to restore the original tree . i . e . , fix the right child of predecessor ; Constructed binary tree is 1 / \ 2 3 / \ 4 5
class Node : NEW_LINE INDENT def __init__ ( self , data , left = None , right = None ) : NEW_LINE INDENT self . data = data NEW_LINE self . left = left NEW_LINE self . right = right NEW_LINE DEDENT DEDENT def morris_traversal ( root ) : NEW_LINE INDENT current = root NEW_LINE while current is not None : NEW_LINE INDENT if current . left is None : NEW_LINE INDENT yield current . data NEW_LINE current = current . right NEW_LINE DEDENT else : NEW_LINE INDENT pre = current . left NEW_LINE while pre . right is not None and pre . right is not current : NEW_LINE INDENT pre = pre . right NEW_LINE DEDENT if pre . right is None : NEW_LINE INDENT pre . right = current NEW_LINE current = current . left NEW_LINE DEDENT else : NEW_LINE INDENT pre . right = None NEW_LINE yield current . data NEW_LINE current = current . right NEW_LINE DEDENT DEDENT DEDENT DEDENT root = Node ( 1 , right = Node ( 3 ) , left = Node ( 2 , left = Node ( 4 ) , right = Node ( 5 ) ) ) NEW_LINE for v in morris_traversal ( root ) : NEW_LINE INDENT print ( v , end = ' ▁ ' ) NEW_LINE DEDENT