PostOrder Traversal

rootNode comes after the children. So left, right, root

Recursive

def postorderOrderTraversal(rootNode: TreeNode) -> None:
    if not rootNode:
        return None

    postorderOrderTraversal(rootNode.left)
    postorderOrderTraversal(rootNode.right)
    visit(rootNode)

Iterative
To pop the parent, we need to check for 2 conditions:

• If there is no right child
• If the right child is already visited
  • To check if the right child is already visited, we need to store the last visited right child in a variable so that next turn we can cross check if we have already visited that children

def postorderOrderTraversalIterative(rootNode: TreeNode) -> None:
    if not rootNode:
        return None

    currNode = rootNode
    stack = deque() # NOTE the stack is empty here
    lastVisitedNode = None

    while stack or currNode:
        while currNode is not None:
            stack.append(currNode)
            currNode = currNode.left

        currNode = stack[-1]

        # If no right child or the right child is explored previously
        if (currNode.right is None or lastVisitedNode == currNode.right):
            visit(stack.pop()) # pop out the current node
            lastVisitedNode = currNode
            currNode = None # IMPORTANT! So that it auto pick the next node
        else:
	        # Else go to the right
	        currNode = currNode.right

Time Complexity

• $O(n)$
  • $n$: number of node in the tree