I wrote post Binary_Tree_Traversal around two years ago to help me remember how to traversal binary tree iteratively. The solution in that post is quite simply. But I still have trouble to remember it since the code pattern is slight different within preorder, inorder, postorder.

Eventually, I rewrite the code using similar pattern in python.

preorder

1 2 3 4 5 6 7 8 9 10 11

classSolution(object): defpreorderTraversal(self, root): rst, stack = [], [] cur = root while cur or stack: while cur: rst.append(cur.val) stack.append(cur.right) cur = cur.left cur = stack.pop() return rst

inorder

1 2 3 4 5 6 7 8 9 10 11 12

classSolution: definorderTraversal(self, root: TreeNode) -> List[int]: rst, stack = [], [] cur = root while cur or stack: while cur: stack.append(cur) cur = cur.left cur = stack.pop() rst.append(cur.val) cur = cur.right return rst

postorder

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

classSolution: defpostorderTraversal(self, root: TreeNode) -> List[int]: rst, stack = [], [] cur = root while cur or stack: while cur: stack.append(cur) cur = cur.left or cur.right cur = stack.pop() rst.append(cur.val) if stack and stack[-1].left == cur: cur = stack[-1].right else: cur = None return rst