# Morris traversal

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    
    def predecessor(self,node):
        # Finds the inorder predecessor of node
        # Go one left and all the way right
        # We add temp.right != node to avoid looping in cycles
	
        cur = node.val
        temp = node.left
        while temp.right is not None and temp.right != node:
            temp = temp.right
        return temp
    
    def helper(self,root):
        curr = root
    
        while curr is not None:
            if curr.left is None:
                # There is no left sub tree, hence we can move 
                # to the right subtree
                # after printing the current node's value
                print(cur.val) 
                curr = curr.right
            else:
            
                pred = self.predecessor(curr) # Inorder predecessor
                
                if pred.right is None:
                    # Assign current node to the right of predecessor
                    # so that after we traverse the left sub tree  
                    # we can come back to the current
                    # node via the predecessor
                    
                    pred.right = curr
                    curr = curr.left
                else:
                    # If pred.right is not None, we must've assigned it
                    # sometime in the past, which means we finished
                    # traversing the left sub tree
                    pred.right = None
                    print(cur.val)
                    curr = curr.right

    
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        self.helper(root)