Binary Tree iterative ordering traversal: preorder, postorder, inorder

tree_traversal.py

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""


class Solution:
    """
    @param root: The root of binary tree.
    @return: Preorder in ArrayList which contains node values.
    """
    def preorderTraversal(self, root):
        ret = []

        stack = []
        while stack or root:
            if root:
                ret.append(root.val)
                if root.right:
                    stack.append(root.right)
                root = root.left
            else:
                root = stack.pop()
        return ret

    def postorderTraversal(self, root):
        ret = []
        stack = []
        
        last = None
        while stack or root:
            if root:
                stack.append(root)
                root = root.left
            else:
                if stack[-1].right and stack[-1].right is not last:
                    root = stack[-1].right
                else:
                    last = stack.pop()
                    ret.append(last.val)
        return ret

    def inorderTraversal(self, root):
        ret = []
        stack = []
        while stack or root:
            if root:
                stack.append(root)
                root = root.left
            else:
                root = stack.pop()
                ret.append(root.val)
                root = root.right
        return ret