post-order traversal
Visiting a node's left subtree, then its right subtree, and the node itself last.
In more detail
Children are always handled before their parent, which is what you need to evaluate an expression tree, total up sizes of folders, or free a tree's memory. Like the other recursive traversals it takes O(n) time and O(h) stack space.
Related terms
- tree traversal — Visiting every node of a tree exactly once in a systematic order.
- pre-order traversal — Visiting a node first, then its left subtree, then its right subtree.
Taught in
- Binary Trees And Their Traversals — Algorithms & Data Structures for Working Engineers