Post-order traversal

Programs that utilize tree strucutres need to process nodes[?] in a tree (represented as circles in below diagram). Nodes contain information about an object. For now, let's assume each node contains a letter.

Post-Order Traversal is a type of Tree Traversal[?] algorithm. Post-order refers to when the root is postponed until its two subtrees are processed.

Steps to Post-order Traversal

Given a non-empty tree,

1. Process the nodes in the left subtree with a recursive call
2. Process the nodes in the right subtree with a recursive call
3. Process the root

Given a binary tree PY:

The order would go D,G,E,B,C,F,A

An example of PostOrder in C++

 template <class Item>
 int postorder_print(const binary_tree_nodes<Item>* ptr)
 // ptr is a pointer to a node in a binary tree OR null
 // meaning empty tree.
 {
    if (ptr != NULL)
    {
        postorder_print( ptr->left() );
        postorder_print( ptr->right() );
        std::cout << ptr->data() << std::endl;
    }
    return 0;
 }

The same example in Haskell might look like

 data Tree a = ET | Node(a, Tree a, Tree a)

 postorder :: Tree a -> [a]
 postorder ET = []
 postorder (Node (x, left,right)) = (postorder left) ++ (postorder right) ++ [x]

Compare: Pre-order traversal, Inorder traversal