Tree Traversals (Inorder, Preorder, Postorder)
Three recursive traversal orders: preorder (root, left, right), inorder (left, root, right), postorder (left, right, root).
PRE-order = announcement before the meeting (root first). IN-order = reading a book left to right (sorted for BST). POST-order = cleaning up after the party (children done first, parent last).
Inorder of a BST yields sorted order — use this to validate a BST. Preorder is useful for serializing/reconstructing a tree (root first means you always know the root before children). Postorder is useful when child results are needed before the parent can be computed (e.g., calculating subtree sizes, tree deletion). Level-order (BFS) gives nodes level by level. Morris traversal achieves O(1) space inorder using threaded binary trees.
Iterative inorder requires explicitly managing the stack: push left children until null, pop, visit, then go right. Iterative postorder is trickier — use two stacks or track 'last visited node' to know when to visit the root after both children. For reconstructing a binary tree: preorder + inorder uniquely determine the tree (preorder gives root, inorder splits left/right subtrees). Same for postorder + inorder. Preorder + postorder does NOT uniquely determine the tree if there are nodes with one child.
I think of traversals by what they solve: inorder for BST properties (sorted output, validation), preorder for serialization/cloning (root available before children), postorder for bottom-up computation (subtree sizes, path sums). When I see 'compute something about each subtree', I immediately think postorder — solve left, solve right, combine at root. For iterative traversal, I can implement inorder with an explicit stack if stack depth is a concern.
Inorder gives sorted output only for a BINARY SEARCH TREE, not a generic binary tree. Also: validating a BST with inorder requires checking the previous value, not just checking left < root < right locally — the local check misses cases where a node is in the wrong subtree.