Binary Tree Inorder Traversal

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

class Solution:
    # @param {TreeNode} root
    # @return {integer[]}
    '''
    # recursive
    def inorderTraversal(self, root):
        if root:
            result=[root.val]
            if root.left:
                result=self.inorderTraversal(root.left)+result
            if root.right:
                result=result+self.inorderTraversal(root.right)
        else:
            result=[]
        return result # returned result will be added
    '''
    # iterative 1
    def inorderTraversal(self,root):
        waitlist,p,result=[],root,[]
        while waitlist or p:
            while p:
                # order in waitlist decide the "inorder"
                waitlist.append(p)
                # find left edge node first
                p=p.left
            p=waitlist.pop()
            result.append(p.val)
            #then right
            p=p.right
        return result
        
    # iterative 2
    def inorderTraversal(self,root):
        if not root:
            return []
        waitlist,result=[(root,False)],[]
        while waitlist:
            p,visited=waitlist.pop()
            if p:
                if visited:
                    result.append(p.val)
                else:
                    waitlist.append((p.right,False))
                    waitlist.append((p,True))
                    waitlist.append((p.left,False))
        return result