There are two families of tree traversal: depth-first (which descends as far as possible before backtracking) and breadth-first (which visits level by level). Depth-first has three sub-orders depending on when you visit the current node relative to its children.
In-order (left, node, right)
For a binary search tree, in-order yields values in sorted order — by far the most common use. Implementation: recursively traverse left, visit, recursively traverse right.
Pre-order (node, left, right)
Visit the root before its children. Used to serialize a tree (the resulting sequence uniquely determines the tree if you mark nulls). Pre-order is what you get from a stack-based iterative traversal.
Post-order (left, right, node)
Visit children before the parent. Used when the result for a node depends on results from its children — deleting a tree, computing subtree sums, evaluating expression trees.
Level-order (BFS)
Visit nodes level by level. Implementation: queue. Enqueue the root; loop: dequeue, visit, enqueue children. Used for shortest-path on unweighted graphs, level statistics, and tree serialization formats like the LeetCode notation.
Iterative vs recursive
Recursive traversals are short and obvious. Iterative versions use an explicit stack (DFS) or queue (BFS) — match the recursive call pattern. Iterative is important when tree depth exceeds the default call stack (10^4 - 10^5 frames typically).
Recursive template
``` function dfs(node): if node is null: return // pre-order: visit(node) here dfs(node.left) // in-order: visit(node) here dfs(node.right) // post-order: visit(node) here ```