Tree traversals

In-order, pre-order, post-order and level-order — see each visiting sequence light up. · 15 min read

Concept

To traverse a tree is to visit every node exactly once in a deliberate order. The order matters because different problems need information at different times. Sometimes you need the parent before the children, sometimes the children before the parent, and sometimes you need nodes level by level.

There are four standard traversal orders. Pre-order, in-order, and post-order are depth-first orders: they go down a branch before coming back. Level-order is breadth-first: it scans the tree row by row.

Mental model

Think of a recursive traversal as a tiny program that reaches a node and has three possible moments to do useful work:

Before visiting children.
Between the left and right child.
After visiting children.

Those three moments produce pre-order, in-order, and post-order. The tree shape is the same; only the location of visit(root) changes.

One skeleton, four behaviours

visit before children — Pre-order: Node, Left, Right.
visit between children — In-order: Left, Node, Right.
visit after children — Post-order: Left, Right, Node.
use a queue instead of recursion — Level-order: process by depth from top to bottom.

Result: Traversal order = where the visit action happens

Depth-first orders

Use this sample tree as a running example:

        8
      /   \
     3     10
    / \      \
   1   6      14

A traversal is not changing the tree. It is deciding the sequence in which these nodes are read.

In-order means Left -> Node -> Right. For the sample BST, the output is 1, 3, 6, 8, 10, 14. On a BST this is sorted because every left subtree contains smaller values and every right subtree contains larger values.

Interactive visualization: In-order → sorted output — step through it frame by frame on this page.

Why the sorted output happens

all left-subtree keys < root — BST ordering invariant.
in-order prints left subtree first — So all smaller keys appear before the root.
then print root — The root sits between smaller and larger keys.
then print right subtree — All larger keys appear after the root.

Result: In-order traversal of a BST is sorted

Pre-order means Node -> Left -> Right. The sample output is 8, 3, 1, 6, 10, 14. This is useful when the parent must be handled before its children, such as copying a tree, saving a tree shape, or printing an outline where headings appear before subitems.

Interactive visualization: Pre-order — step through it frame by frame on this page.

Post-order means Left -> Right -> Node. The sample output is 1, 6, 3, 14, 10, 8. This is useful when the parent answer depends on child answers: deleting a tree, computing subtree sizes, evaluating expression trees, or doing dynamic programming on trees.

Interactive visualization: Post-order — step through it frame by frame on this page.

Breadth-first order

Level-order visits nodes by depth using a queue. The sample output is 8, 3, 10, 1, 6, 14: root first, then depth 1, then depth 2. This is breadth-first search on a tree, and it is the natural order for shortest-depth questions.

Interactive visualization: Level-order (BFS) — step through it frame by frame on this page.

C++ templates

The depth-first versions differ only in where the visit(root) line is placed. That is the most important pattern to remember:

void preorder(Node* root) {
    if (!root) return;
    visit(root);              // before children
    preorder(root->left);
    preorder(root->right);
}

void inorder(Node* root) {
    if (!root) return;
    inorder(root->left);
    visit(root);              // between left and right
    inorder(root->right);
}

void postorder(Node* root) {
    if (!root) return;
    postorder(root->left);
    postorder(root->right);
    visit(root);              // after children
}

BFS/level-order replaces recursion with an explicit queue:

void levelOrder(Node* root) {
    if (!root) return;
    queue<Node*> q;
    q.push(root);

    while (!q.empty()) {
        Node* u = q.front(); q.pop();
        visit(u);
        if (u->left) q.push(u->left);
        if (u->right) q.push(u->right);
    }
}

Choosing the order

A good rule of thumb:

Need sorted values from a BST? Use in-order.
Need to create, copy, serialize, or print a hierarchy top-down? Use pre-order.
Need child results before parent results? Use post-order.
Need nearest-by-depth, level grouping, or minimum number of edges from the root? Use level-order/BFS.

Complexities

Why every traversal is linear

Visit every node exactly once

each node is enqueued/called once — The traversal reaches every node from exactly one parent.
each node is visited once — The output action happens one time per node.
n nodes × constant work — Ignoring child-pointer checks, the work scales with node count.

Result: O(n)

Practice: Inorder Traversal (Easy) — Visit left, node, right — return the value sequence.

Practice: Level-Order Traversal (Medium) — Group node values by depth using a BFS queue.

Practice: Zigzag Level-Order (Hard) — Level-order, but alternate left→right and right→left per level.