Pre-order traversal

Pre-order traversal is a depth-first walk of a Binary tree that visits each node before its children: process the current node, then recursively traverse the left subtree, then the right. The acronym NLR (Node-Left-Right) captures the order.

preorder(root) → root, then preorder(left), then preorder(right)

It’s the natural choice when the parent’s information needs to be processed before the children’s — copying a tree, serialising it for transmission, or producing prefix expression output.

Recursive implementation

void preorderPrint(BinaryTreeNode *cur) {
    if (cur == NULL) return;
    printf("%d ", cur->data);              // process current
    preorderPrint(cur->left);              // then left subtree
    preorderPrint(cur->right);             // then right subtree
}

The order of the three statements is the only difference between pre-, in-, and post-order. Move the print line to the middle for in-order, to the end for post-order.

Worked example

Take the standard sorted binary tree: root F; F’s children are B (left) and G (right); B’s children are A and D; D’s children are C and E; G has right child I, whose left child is H. Pre-order visits each node the moment it is first reached (shown by the arrows hitting the left of each node):

Image: Sorted binary tree showing pre-order traversal, public domain

Pre-order output: F B A D C E G I H

Trace:

1. Visit F. Recurse left into B.
2. Visit B. Recurse left into A.
3. Visit A. Both children NULL — return.
4. Back at B. Recurse right into D.
5. Visit D. Recurse left into C (leaf) — return. Recurse right into E (leaf) — return.
6. Back at F. Recurse right into G.
7. Visit G. Left is NULL. Recurse right into I.
8. Visit I. Recurse left into H (leaf) — return.

Final sequence: F B A D C E G I H.

Iterative implementation with an explicit stack

The recursion uses the call stack. To do it iteratively, simulate that stack:

void preorderIterative(BinaryTreeNode *root) {
    if (root == NULL) return;
    Stack s = stack_create();
    stack_push(&s, root);
    while (!stack_empty(&s)) {
        BinaryTreeNode *cur = stack_pop(&s);
        printf("%d ", cur->data);
        if (cur->right) stack_push(&s, cur->right);   // right first
        if (cur->left)  stack_push(&s, cur->left);    // so left pops first
    }
}

Push right before left so left is popped first — preserving root, left, right order. Same time complexity, but explicit memory rather than the call stack.

Use cases

• Tree copying. To copy a tree into a new structure, you need to create the parent node before its children — pre-order matches that.
• Serialisation / deserialisation. Writing a tree to disk in pre-order with NULL markers (F B A # # D C # # E # # G # I H # # #) lets you reconstruct it by reading nodes in the same order. Used in interview questions and JSON tree formats.
• Prefix (Polish) notation. Pre-order traversal of an expression tree produces prefix notation: $(a+b)\cdot c$ becomes * + a b c.
• Directory listing. Print a folder before its contents — recursively descend and print each directory then its children.
• DFS variant. Pre-order is the binary-tree case of DFS’s “visit on first encounter” timing.

Complexity

Time: $O(n)$ — each of $n$ nodes is processed once. Space: $O(h)$ for the recursion stack, where $h$ is the tree height. For a balanced tree, $h=O(\log n)$; for a degenerate (linked-list-like) tree, $h=O(n)$.

The iterative version uses the same $O(h)$ stack space — just an explicit data structure instead of the call stack.

Comparison with the other orders

The four standard binary-tree traversals differ only in when the current node is visited and what data structure drives the walk:

Order	Sequence	Driver	Use cases
Pre-order	Root, Left, Right	Stack / call stack	Copying, serialisation, prefix output
In-order	Left, Root, Right	Stack	BST sorted output
Post-order	Left, Right, Root	Stack	Deletion, postfix, recursive metrics
Level-order	By depth, left-to-right	Queue	Shortest paths, layer processing

For the hub linking all four, see Binary tree traversal.