Postordre

Postordre is the French term for postorder traversal, a depth-first approach used to visit nodes in a tree. In this traversal, each node is processed after all of its descendants. In a binary tree, the common order is left subtree, right subtree, then the node itself. For general trees, the procedure visits each child subtree before the node.

Implementation can be done recursively or iteratively. A recursive version calls postorder on the left child, then the right child, and finally processes the node. Iterative implementations typically use a stack; common variants include using two stacks or a single stack with a marker for the last visited node to ensure a node is processed only after its children.

The time complexity of postorder traversal is O(n), where n is the number of nodes. The space complexity is O(h), with h representing the height of the tree; this is the maximum depth of the call stack in a recursive approach or the stack size in an iterative approach. In balanced trees, h is logarithmic in n, while in degenerate trees it can be linear in n.

Postorder traversal has several practical uses. It is natural for bottom-up processing tasks, such as deleting a tree or freeing resources, because it visits children before their parent. It is also fundamental in evaluating expression trees, where a postorder sequence corresponds to a postfix (reverse Polish) form that can be evaluated from left to right. The postorder order is one of the three classic depth-first traversals, alongside preorder and inorder, each with distinct visit orders and applications.