Trees/Postorder
From charlesreid1
Contents
Postorder traversal in trees
Postorder traversal is a depthfirst recursive tree traversal algorithm that can be defined and applied recursively to Trees, very similar to Trees/Preorder (preorder traversal). Postorder is a bottomup traversal, where the visit action is performed as the recursive functions return off the stack.
Recursive definition
As with any recursive method, this must be split into a base case and a recursive case. The base case is, we've reached an external node  no children. The recursive case is, we call preorder on each child. In this case we don't need an explicit base case and recursive case.
The postorder traversal is the patient, waitandsee heuristic.
Here is an example of a postorder traversal pseudocode:
define public function postorder( tree ) postorder_subtree( tree, root, 0 ) define private function postorder_subtree( tree, position, depth) for child in position.children(): postorder_subtree(tree, child, depth+1) perform visit action on position
Because this is an intransitive recursive function  nothing is returned  the base case can remain implicit (if position is an external node, position.children is empty, and the for loop is not run, and an instance of the void recursive method returns).
Implementation
The implementation of postorder traversal is implemented in the linked binary tree class Binary Trees/LinkedBinTree using the following methods:
 A public method that takes no parameters,
postorder()
, returning an iterator over each node in postorder traversal order: https://charlesreid1.com:3000/cs/java/src/master/trees/LinkedBinTree.java#L397  A private method that takes two parameters, one position and one Collections object (a list) to store a list of items for the iterator to return back: https://charlesreid1.com:3000/cs/java/src/master/trees/LinkedBinTree.java#L404
All the work is done by the second method. It is a recursive method that iterates over each child, recursively calling itself on each child, then adds the current node to the list when finished running on each child.
/** Utility method for postorder tree traversal. */ private void postorderSubtree(Position<E> p, List<Position<E>> snapshot) { // 1. Recurse through children for(Position<E> c : children(p)) { postorderSubtree(c,snapshot); } // 2. Perform visit action for Position p snapshot.add(p); }
Related Pages
Graphs:
 Graphs#Graph Traversals
 Graphs/Depth First Traversal
 Graphs/Breadth First Traversal
 Graphs/Euler Tour
Traversals on trees:
 Trees/Preorder
 Trees/Postorder
 Trees/Inorder
Breadthfirst search and traversal on trees:
Depthfirst search and traversal on trees:
OOP design patterns:
Flags
Trees Part of Computer Science Notes
Series on Data Structures Abstract data type: Trees/ADT Concrete implementations: Trees/LinkedTree · Trees/ArrayTree · SimpleTree
Tree Traversal Preorder traversal: Trees/Preorder Postorder traversal: Trees/Postorder InOrder traversal: Binary Trees/Inorder BreadthFirst Search: BFS BreadthFirst Traversal: BFT DepthFirst Search: DFS DepthFirst Traversal: DFT OOP Principles for Traversal: Tree Traversal/OOP · Tree Traversal/Traversal Method Template Tree operations: Trees/Operations Performance · Trees/Removal
Tree Applications Finding Minimum in Log N Time: Tree/LogN Min Search
Abstract data type: Binary Trees/ADT Concrete implementations: Binary Trees/LinkedBinTree · Binary Trees/ArrayBinTree Binary Trees/Cheat Sheet · Binary Trees/OOP · Binary Trees/Implementation Notes
