How to inorder traversal a BST tree without using extra space.

inorder_wo_space.py

# Helpers start
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = self.right = None

def get_tree():
    '''
        4
       / \
      2   6
     / \
    1   3
    '''
    root = TreeNode(4)
    root.left = TreeNode(2)
    root.right = TreeNode(6)
    root.left.left = TreeNode(1)
    root.left.right = TreeNode(3)
    return root
# Helpers end


class Traversal:
    @staticmethod
    def inorder(root):
        '''
        parent pointer +  done flag
        '''
        root.parent = None
        curt = root
        while curt:
            if curt.left and not hasattr(curt.left, 'done'):
                curt.left.parent = curt
                curt = curt.left
            elif hasattr(curt, 'done'):
                if curt.right and not hasattr(curt.right, 'done'):
                    curt.right.parent = curt
                    curt = curt.right
                else:
                    curt = curt.parent
            else:
                print(curt.val,)
                curt.done = True



if __name__ == '__main__':
    root = get_tree()
    Traversal.inorder(root)
    # 1,2,3,4,6,