Tree Traversals (DFS): Pre-order, In-order & Post-order

A traversal is a systematic way to visit every node of a tree exactly once. The depth-first family dives as deep as possible along one branch before backtracking, and comes in three flavours — pre-order, in-order, and post-order — that differ only in when you process the current node relative to its subtrees. All three run in O(n) time.

We use the standard TreeNode from earlier in this section.

The three DFS orders

For each node you do three things — visit the node (N), recurse left (L), recurse right (R) — and the order of those steps names the traversal:

• Pre-order (N, L, R): process the node before its children. Great for copying a tree or printing a prefix expression.
• In-order (L, N, R): process the node between its subtrees. On a BST this yields nodes in sorted order.
• Post-order (L, R, N): process the node after its children. Used to delete/free a tree or evaluate an expression tree.

        (1)
       /   \
     (2)    (3)
     / \
   (4) (5)

Pre-order:  1 2 4 5 3
In-order:   4 2 5 1 3
Post-order: 4 5 2 3 1

Recursive traversal

The recursive versions are the clearest — each is the three steps in a different order. Here is in-order:

void inorder(TreeNode* root, std::vector<int>& out) {
    if (root == nullptr) return;
    inorder(root->left, out);
    out.push_back(root->val);
    inorder(root->right, out);
}

void inorder(TreeNode root, List<Integer> out) {
    if (root == null) return;
    inorder(root.left, out);
    out.add(root.val);
    inorder(root.right, out);
}

function inorder(root, out = []) {
  if (root === null) return out;
  inorder(root.left, out);
  out.push(root.val);
  inorder(root.right, out);
  return out;
}

def inorder(root, out=None):
    if out is None:
        out = []
    if root is None:
        return out
    inorder(root.left, out)
    out.append(root.val)
    inorder(root.right, out)
    return out

To get pre-order, move the visit line above the left recursion; for post-order, move it below the right recursion. That single move is the whole difference.

Iterative traversal (with an explicit stack)

Recursion uses the call stack implicitly. To avoid stack-overflow on very deep trees — or just to show you understand the mechanics — emulate it with an explicit stack. Here is iterative in-order: push left nodes, then pop and go right.

std::vector<int> inorderIter(TreeNode* root) {
    std::vector<int> out;
    std::stack<TreeNode*> st;
    TreeNode* cur = root;
    while (cur != nullptr || !st.empty()) {
        while (cur != nullptr) { st.push(cur); cur = cur->left; }
        cur = st.top(); st.pop();
        out.push_back(cur->val);
        cur = cur->right;
    }
    return out;
}

List<Integer> inorderIter(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    Deque<TreeNode> st = new ArrayDeque<>();
    TreeNode cur = root;
    while (cur != null || !st.isEmpty()) {
        while (cur != null) { st.push(cur); cur = cur.left; }
        cur = st.pop();
        out.add(cur.val);
        cur = cur.right;
    }
    return out;
}

function inorderIter(root) {
  const out = [], st = [];
  let cur = root;
  while (cur !== null || st.length > 0) {
    while (cur !== null) { st.push(cur); cur = cur.left; }
    cur = st.pop();
    out.push(cur.val);
    cur = cur.right;
  }
  return out;
}

def inorder_iter(root):
    out, st = [], []
    cur = root
    while cur is not None or st:
        while cur is not None:
            st.append(cur)
            cur = cur.left
        cur = st.pop()
        out.append(cur.val)
        cur = cur.right
    return out

For beginners: Iterative pre-order is even simpler — push the root, then pop a node, record it, and push its right then left child so the left is processed first.

Complexity

Here h is the tree height: O(log n) when balanced, O(n) when skewed.

Going deeper: All three DFS orders visit nodes in the same physical sweep — only the moment of recording each node changes. Internalizing that makes converting between them trivial.

Next steps

DFS goes deep; the complementary strategy goes wide. Learn level-order traversal (BFS) next, then see in-order’s payoff on binary search trees.