Pre-order, In-order, Post-order & Level-order

A traversal is simply a rule for the order in which you visit every node in a tree exactly once. That sounds like a small detail, but different traversals unlock different guarantees and different use cases - the "right" traversal depends entirely on what you are trying to do with the tree. Three of the four traversals below are variations on depth-first search (go deep before going wide), and differ only in when they record the current node relative to recursing into its children. The fourth, level-order, is breadth-first instead, and needs a fundamentally different tool to implement.

Pre-order records the current node before recursing into either child. This is the traversal to reach for when you want to reconstruct or clone a tree from scratch, since a parent is always emitted before its children - reading the output back in the same order naturally rebuilds the same shape.

In-order visits the entire left subtree, then the current node, then the entire right subtree. Applied to a BST specifically, this produces every value in fully sorted order - a direct consequence of the invariant from the previous module: everything to the left is smaller, everything to the right is larger, so visiting left-node-right at every level threads the values together in ascending order.

Post-order visits both children fully before recording the current node. This ordering is what makes it the safe choice for deleting or freeing an entire tree: by the time a node is processed, both of its children have already been fully handled, so there is never a dangling reference to a child you have not dealt with yet. The same idea shows up in evaluating expression trees, where an operator node needs both of its operand subtrees fully evaluated first.

The first three traversals are all depth-first - they follow one branch all the way down before backtracking, which is exactly the shape recursion (and its implicit call stack) naturally provides. Level-order is different: it visits every node at depth 0, then every node at depth 1, then depth 2, and so on - breadth, not depth, first. Recursion has no natural way to pause a branch and jump to a sibling at the same level, so level-order needs an explicit FIFO queue instead: enqueue the root, then repeatedly dequeue a node, record it, and enqueue its children (in left-to-right order) for later.