TreeTraverseConstSpace

def inOrderTraverse(root):
    if root is None:
        return []

    result = []
    cur_node = root

    visit_left = True
    while True:
        if visit_left:
            visit_left = False
            while cur_node.left is not None:
                cur_node = cur_node.left
        else:
            result.append(cur_node.val)
            if cur_node.right is not None:
                visit_left = True
                cur_node = cur_node.right
            else:
                visit_left = False
                target_parent = None
                while cur_node.parent is not None:
                    if cur_node.parent.left == cur_node:
                        target_parent = cur_node.parent
                        break
                    cur_node = cur_node.parent
                if target_parent is None:
                    break
                cur_node = target_parent
    return result

def inOrderReverseTraverse(root):
    if root is None:
        return []

    result = []
    cur_node = root

    visit_right = True
    while True:
        if visit_right:
            visit_right = False
            while cur_node.right is not None:
                cur_node = cur_node.right
        else:
            result.append(cur_node.val)
            if cur_node.left is not None:
                visit_right = True
                cur_node = cur_node.left
            else:
                visit_right = False
                target_parent = None
                while cur_node.parent is not None:
                    if cur_node.parent.right == cur_node:
                        target_parent = cur_node.parent
                        break
                    cur_node = cur_node.parent
                if target_parent is None:
                    break
                cur_node = target_parent
    return result