Postorder traversal visits every node in a nested structure exactly once, processing children before their parent. This makes it useful when a parent depends on already-processed branch results, such as reducing a tree or evaluating an expression. section 8.4 section 8.4.1
In Clojure, clojure.walk/postwalk applies a one-argument function throughout an arbitrarily nested form:
- The function runs after reaching an innermost item and after recursively processing nested collections. section 8.4.2
- The input may be any type, including nil; collections are recursively traversed, while unsupported collection implementations may raise UnsupportedOperationException. section 8.4.2
- The result depends on the transformation function and generally retains the input collection type. section 8.4.2
- Unlike prewalk, postwalk cannot alter a branch before descending into it; it is suited to processing the completed branch before its parent. section 8.4.1
Evaluating an expression tree
Represent an expression with operator nodes and operand branches, then evaluate children before their parent: (postwalk evaluate (compound-interest-data 7.2 5000 2)) returns 5771.936460924754. Each nested function application becomes a value before the enclosing function receives it. section 8.4.2
Figure 8.12. Depth-first, post-order traversal of a simple tree. The continuous line shows the traversal path, while the little cameras represent the call to the visiting function.
Use the traversal diagram to follow the depth-first path: leaves are visited first, followed by enclosing collections as traversal moves back upward. section 8.4.1
