# Simple Python iterative solution by using a visited flag - O(n) 56ms

• ``````# 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``````

• Great solution. can you extend such methods to pre-order and post-order search?

• i like it ~ thank you~

• Could you explain why go node.right first and then node.left? since for the recursive code, it's node.left, res.append(node.val), node.right. Why is it the other way around for iterative

• @pennlio Simply change (cur.right, cur, cur.left) triplet

in-order: (cur.right, cur, cur.left)
pre-order: (cur.right, cur.left, cur)
post-order: (cur, cur.right, cur.left)

• Brilliant answer. Easy to extend to pre-order and post-order cases.
I wonder why this answer has so few up-votes.

• If you think about it, there are more stack operations than other solutions. Each node will be pushed-popped-pushed-popped.

• @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!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.