PostOrder Traversal

Traverse the left subtree first, then the right subtree and after that visit the parent node. For example,

336px-Sorted_binary_tree_postorder.svg

 

PostOrder: A, C, E, D, B, H, I, G, F

Recursive Algorithm

postorder(node)
  if node == null then return
  postorder(node.left)
  postorder(node.right)
  visit(node)

Iterative Algorithm

Postorder(node)
  parentStack = empty stack  
  lastnodevisited = null 
  while (not parentStack.isEmpty() or node ≠ null)
    if (node ≠ null)
      parentStack.push(node)
      node = node.left
    else
      peeknode = parentStack.peek()
      if (peeknode.right ≠ null and lastnodevisited ≠ peeknode.right) 
        /* if right child exists AND traversing node from left child, move right */
        node = peeknode.right
      else
        visit(peeknode)
        lastnodevisited = parentStack.pop()