Preorder traversal (root → left → right) is used to copy trees and prefix expressions. Postorder traversal (left → right → root) is used to delete trees and evaluate postfix expressions. Together with inorder, these three traversals fully characterize any tree.
void preorder(Node* root, vector<int>& res) {
if (!root) return;
res.push_back(root->val);
preorder(root->left, res);
preorder(root->right, res);
}
void postorder(Node* root, vector<int>& res) {
if (!root) return;
postorder(root->left, res);
postorder(root->right, res);
res.push_back(root->val);
}Preorder visits the current node before its children. This is useful for creating a copy of the tree, serializing a tree, or generating prefix (Polish) notation of an expression tree.
Postorder visits children before the current node. This is used when you need to process all descendants before the parent — deleting a tree, evaluating postfix expressions, or computing directory sizes.
Given any two of {inorder, preorder, postorder}, you can uniquely reconstruct the original binary tree (as long as all values are distinct). This is a classic tree reconstruction problem.
Quiz coming soon for this algorithm.