Post-Order Traversal

overview

Summary

post_order_traversal visits a tree as: left_subtree, right_subtree, then root. It is a depth_first_search used on a binary_tree or general tree. Recursive versions use recursion and the call stack. Iterative versions use a stack, sometimes two stacks or a marker for a previous node. It runs in time_complexity O(n) and space_complexity O(h), where h is tree height. Common uses include deletion of a tree and expression_evaluation with an expression tree.