# 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[]}
def inorderTraversal(self, root):
result, stack = [], [(root, False)]
while stack:
cur, visited = stack.pop()
if cur:
if visited:
result.append(cur.val)
else:
stack.append((cur.right, False))
stack.append((cur, True))
stack.append((cur.left, False))
return result
Simple Python iterative solution by using a visited flag  O(n) 56ms


@pennlio Simply change (cur.right, cur, cur.left) triplet
inorder: (cur.right, cur, cur.left)
preorder: (cur.right, cur.left, cur)
postorder: (cur, cur.right, cur.left)

@edcccccch We are using a stack, we want to make sure that left node is processed before right as needed in inorder traversal. (left>parent>right)
As stack is LIFO, we first add right node and then left.
Hope this helps!