Morris traversal for Preorder | Python program for Morris Preorder traversal A binary tree Node ; Preorder traversal without recursion and without stack ; If left child is null , print the current node data . And , update the current pointer to right child . ; Find the inorder predecessor ; If the right child of inorder predecessor already points to the current node , update the current with it 's right child ; else If right child doesn ' t ▁ point ▁ ▁ to ▁ the ▁ current ▁ node , ▁ then ▁ print ▁ this ▁ ▁ node ' s data and update the right child pointer with the current node and update the current with it 's left child ; Function for sStandard preorder traversal ; Driver program to test
class Node : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . data = data NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def MorrisTraversal ( root ) : NEW_LINE INDENT curr = root NEW_LINE while curr : NEW_LINE INDENT if curr . left is None : NEW_LINE INDENT print ( curr . data , end = " ▁ " ) NEW_LINE curr = curr . right NEW_LINE DEDENT else : NEW_LINE INDENT prev = curr . left NEW_LINE while prev . right is not None and prev . right is not curr : NEW_LINE INDENT prev = prev . right NEW_LINE DEDENT if prev . right is curr : NEW_LINE INDENT prev . right = None NEW_LINE curr = curr . right NEW_LINE DEDENT else : NEW_LINE INDENT print ( curr . data , end = " ▁ " ) NEW_LINE prev . right = curr NEW_LINE curr = curr . left NEW_LINE DEDENT DEDENT DEDENT DEDENT def preorfer ( root ) : NEW_LINE INDENT if root : NEW_LINE INDENT print ( root . data , end = " ▁ " ) NEW_LINE preorfer ( root . left ) NEW_LINE preorfer ( root . right ) NEW_LINE DEDENT DEDENT root = Node ( 1 ) NEW_LINE root . left = Node ( 2 ) NEW_LINE root . right = Node ( 3 ) NEW_LINE root . left . left = Node ( 4 ) NEW_LINE root . left . right = Node ( 5 ) NEW_LINE root . right . left = Node ( 6 ) NEW_LINE root . right . right = Node ( 7 ) NEW_LINE root . left . left . left = Node ( 8 ) NEW_LINE root . left . left . right = Node ( 9 ) NEW_LINE root . left . right . left = Node ( 10 ) NEW_LINE root . left . right . right = Node ( 11 ) NEW_LINE MorrisTraversal ( root ) NEW_LINE print ( " " ) NEW_LINE preorfer ( root ) NEW_LINE