How Pre-Order Traversal Works

Pre-order traversal visits a node before its subtrees. That order is what you need to copy a tree or serialise it, because a parent always arrives before the children that hang off it.

Output so far

Nothing yet.

Not reached
On the stack
Current
Visited

Speed

Step 1 of 13

Pre-order walk over 7 values, 3 levels deep.

Counters

Visited: 0/7
On the stack: 0
Tree height: 3
Nodes: 7

Settings

How many values7

How it was built

Pre-order

1stack = [root]
2while stack:
3 node = stack.pop()
4 visit(node)
5 push node.right
6 push node.left

What each walk is for

Walk	What you get	Time	Extra space
In-order	Values in sorted order	O(n)	O(h)
Pre-order	Root before children, for copying a tree	O(n)	O(h)
Post-order	Children before root, for freeing or evaluating	O(n)	O(h)
Level-order	Shallowest nodes first, level by level	O(n)	O(w)
Search	One value, by comparing at each node	O(h)	O(1)

n is the number of values, h the height of the tree and w its widest level. Build the tree from sorted values and h grows all the way to n — that is what balancing prevents.

Complexity

Best	Average	Worst	Extra memory
O(n)	O(n)	O(n)	O(h)

Same n and h as every other traversal. What differs is the order the nodes come out in, and therefore what you can reconstruct from the sequence.

How pre-order traversal works

Pre-order traversal emits the current node, then walks the left subtree, then the right. Because every parent is emitted before its descendants, the resulting sequence can be replayed to rebuild the tree with the same structure — insert them in that order and you get the original shape back. In-order cannot do that: its output is sorted, and sorted input builds a completely different tree.

If the node is empty, return.
Visit the node — emit it now, before looking at any child.
Traverse the left subtree in full.
Traverse the right subtree in full.

Implementation

The same algorithm the visualiser is running, written to be read.

def pre_order(node, visit):
    if node is None:
        return
    visit(node.value)          # parent before children
    pre_order(node.left, visit)
    pre_order(node.right, visit)


def pre_order_iterative(root):
    out, stack = [], [root] if root else []
    while stack:
        node = stack.pop()
        out.append(node.value)
        # Right pushed first, so left is processed first.
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return out

When to use it

Use it to copy or serialise a tree, and to send one over a wire: replaying the sequence rebuilds the same structure.
Use it for anything that must process a parent before its children — evaluating an expression tree top-down, rendering a nested layout, applying inherited settings down a hierarchy.
Avoid it when you need sorted output from a BST; that is in-order.

Check yourself

If the animation made sense, these should too.

Why can a tree be rebuilt from its pre-order sequence but not from its in-order one?

Pre-order emits every parent before its descendants, so replaying the sequence as inserts reproduces the same structure. In-order output is sorted, and inserting sorted values builds a degenerate chain - the values survive, the shape does not.

Which traversal suits applying inherited state down a hierarchy?

Pre-order. The parent is visited before its children, so whatever it computes - an accumulated transform, a resolved permission, a CSS-like inherited value - is available by the time the children are reached.