Binary Tree Pre-Order Traversal, in depth: the rule, the right-then-left stack traced step by step, null-marker serialization and top-down state

The rule, and what visiting parents first buys you

Every depth-first traversal visits the same nodes along the same path; what differs is when each node is reported. Pre-order reports a node the first time the walk reaches it, before going down. In-order reports it between the two subtrees, and post-order after both.

That timing gives pre-order one defining property: every node appears before all of its descendants. A parent is always processed before its children. So anything a child needs from its parent, such as a depth, a path, an accumulated sum or a newly allocated copy of the parent to attach itself to, is already available when the child is processed. Post-order has the opposite property, children before parents, which suits computations flowing upward, such as subtree sizes or freeing memory.

The other consequence is that the first element of a pre-order sequence is always the root, and the first element of any subtree's slice is that subtree's root. That is why pre-order, combined with enough extra information, identifies a tree uniquely.

The example tree

The tree has root F. F's left child is B, whose children are A and D; D has children C and E. F's right child is G, which has only a right child I, and I has only a left child H. The pre-order sequence is F, B, A, D, C, E, G, I, H. Trace it once by hand with the rule node, left, right before reading the code, because every bug discussed later shows up as a deviation from that sequence.

The recursive walk

The recursive version is a direct transcription of the rule:

class Node:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def preorder(node, out):
    if node is None:
        return
    out.append(node.val)        # visit first
    preorder(node.left, out)
    preorder(node.right, out)

def build_example():
    return Node("F",
        Node("B", Node("A"), Node("D", Node("C"), Node("E"))),
        Node("G", None, Node("I", Node("H"))))

seq = []
preorder(build_example(), seq)
assert seq == list("FBADCEGIH")

It runs in O(n) time, since each node is entered once, and uses O(h) stack space, where h is the height. For a balanced tree h is about log2 n; for a degenerate tree that is really a linked list, h equals n. Python's default recursion limit is 1,000, so a skewed tree of a few thousand nodes, which is easy to produce by inserting sorted keys into an unbalanced binary search tree, raises RecursionError. Java and C++ have larger but still finite thread stacks and fail with a stack overflow instead. Any code that walks trees built from untrusted or unbounded input needs the iterative version.

The explicit stack, traced

The iterative version replaces the call stack with an explicit one. Pop a node, visit it, then push its children. A stack is last in, first out, so to visit the left child first you push the right child first.

def preorder_iter(root):
    out, stack = [], [root] if root else []
    while stack:
        node = stack.pop()
        out.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)   # pushed last, popped next
    return out

assert preorder_iter(build_example()) == list("FBADCEGIH")

Here is the trace on the example, with the top of the stack on the right:

The output is F B A D C E G I H, matching the recursive version. The stack never held more than three nodes. In general this version holds at most one pending right child per level, so its space is O(h) as well, but it lives on the heap, where a million entries is a few megabytes rather than a crash.

If you need the walk to stop early, for example to find the first node matching a predicate, or to process an enormous tree lazily, turn it into a generator. The caller pulls one node at a time and can stop whenever it likes, and the remaining stack is simply discarded:

def iter_preorder(root):
    stack = [root] if root else []
    while stack:
        node = stack.pop()
        yield node
        if node.right: stack.append(node.right)
        if node.left:  stack.append(node.left)

first_leaf = next(n for n in iter_preorder(build_example())
                  if n.left is None and n.right is None)
assert first_leaf.val == "A"

There is also a constant-space version that threads temporary links through the tree, Morris traversal. It changes one line of the in-order algorithm and is covered with the rest of that family in Morris traversal.

Serializing a tree with null markers

A bare pre-order sequence does not determine a tree. The sequence A, B fits B as A's left child and B as A's right child. Add a marker for every empty child and the ambiguity disappears: each node is followed by the full encoding of its left subtree, then the full encoding of its right subtree, so the reader always knows where a subtree ends. A tree with n nodes has exactly n plus 1 empty child slots, so the encoding has 2n plus 1 tokens.

With # as the marker, the example tree serializes to F B A # # D C # # E # # G # I H # # #: nine nodes and ten markers. Reading it back is pre-order again, consuming tokens from the front:

def serialize(root):
    out = []
    stack = [root]
    while stack:
        node = stack.pop()
        if node is None:
            out.append("#")
            continue
        out.append(str(node.val))
        stack.append(node.right)
        stack.append(node.left)
    return " ".join(out)

def deserialize(s):
    tokens = iter(s.split())
    def build():
        tok = next(tokens)
        if tok == "#":
            return None
        node = Node(tok)
        node.left = build()
        node.right = build()
        return node
    root = build()
    if next(tokens, None) is not None:
        raise ValueError("trailing tokens: not a valid encoding")
    return root

s = serialize(build_example())
assert s == "F B A # # D C # # E # # G # I H # # #"
assert serialize(deserialize(s)) == s

The serializer is iterative so that deep trees serialize safely; the deserializer shown is recursive for clarity and has the same depth limit as before, so production code converts it to an explicit stack of parents waiting for a child. Values containing spaces or the marker need escaping or a length-prefixed format; JSON arrays avoid that problem at the cost of size.

This is the same idea behind many real formats. A file archive lists a directory before its contents. A syntax tree printed in prefix notation, such as a Lisp expression, is a pre-order walk. When you only have two traversals without null markers, rebuilding needs pre-order plus in-order and unique values; that construction is covered in building a tree from its traversals.

Top-down problems: carrying state on the stack

Because parents come first, pre-order is the natural shape for problems where each node needs state derived from its ancestors. Carry that state on the stack alongside the node, so each entry is a pair of node and state. Three common examples:

def print_tree(root):
    # Directory-style listing: depth comes from the parent.
    stack = [(root, 0)]
    while stack:
        node, depth = stack.pop()
        if node is None:
            continue
        print("  " * depth + str(node.val))
        stack.append((node.right, depth + 1))
        stack.append((node.left, depth + 1))

def root_to_leaf_paths_with_sum(root, target):
    # Every root-to-leaf path whose values sum to target.
    found, stack = [], [(root, 0, ())] if root else []
    while stack:
        node, total, path = stack.pop()
        total, path = total + node.val, path + (node.val,)
        if node.left is None and node.right is None and total == target:
            found.append(path)
        if node.right: stack.append((node.right, total, path))
        if node.left:  stack.append((node.left, total, path))
    return found

def clone(root):
    # Copy: the parent's copy exists before its children are attached.
    if root is None:
        return None
    new_root = Node(root.val)
    stack = [(root, new_root)]
    while stack:
        src, dst = stack.pop()
        if src.right:
            dst.right = Node(src.right.val); stack.append((src.right, dst.right))
        if src.left:
            dst.left = Node(src.left.val);   stack.append((src.left, dst.left))
    return new_root

The path example copies a tuple per node, which costs O(h) per step; when paths are long, keep one shared list and append on the way down and pop on the way back up, which needs the recursive form or an explicit enter and exit marker. The pattern generalises to N-ary trees by pushing children in reverse order, which is exactly how a file-system walker lists a directory's entries in sorted order.

Failure modes

• Pushing left before right. The iterative version then emits node, right, left. On the example it produces F G I H B D E C A. A test on a symmetric tree will not catch this; use an asymmetric one.
• Pushing None without handling it. Popping a null and dereferencing it crashes. Either guard every push, as the plain version does, or handle nulls at pop time, as the serializer does, but not half of each.
• Recursion depth. Recursive walks pass every test on balanced trees and fail in production on a skewed one. Test with a 100,000-node chain.
• Mutating the tree mid-walk. Deleting or re-parenting nodes while a traversal holds them on the stack visits removed nodes or skips moved ones. Collect first, then mutate.
• Encoding without markers. Storing a pre-order list without null markers and rebuilding by inserting into a BST only works if the tree really was a BST built from that order. Anything else silently changes shape.
• Unescaped values. A value equal to the marker, or containing the separator, corrupts the encoding. Escape, length-prefix or use JSON.

Testing traversal code

Traversal code is easy to test well, because the recursive version is short enough to trust and can serve as the oracle for every faster or iterative one. Generate random trees of many shapes, including chains in both directions, and compare:

import random

def random_tree(n, rng):
    if n == 0:
        return None
    left = rng.randint(0, n - 1)
    return Node(rng.randint(0, 9), random_tree(left, rng), random_tree(n - 1 - left, rng))

rng = random.Random(7)
for _ in range(2000):
    t = random_tree(rng.randint(0, 40), rng)
    expected = []
    preorder(t, expected)
    assert preorder_iter(t) == expected
    assert serialize(deserialize(serialize(t))) == serialize(t)

Add three properties: the first element is the root's value; the output has exactly n elements; and for the serializer, the token count is 2n plus 1. Add one deep chain built in a loop to prove the iterative paths never recurse. Watch the duplicated values in the random trees: the serializer handles them, while anything that rebuilds from two traversals does not.

For more on depth-first search in general, including how the same explicit-stack idea applies to graphs with visited sets, see iterative DFS with a stack. For the in-order sibling of this page, with its own stack trace and iterator, see in-order traversal.

What to do next

1. Write the recursive and iterative versions from memory and run both on the nine-node example; the output must be F B A D C E G I H.
2. Swap the two push lines deliberately, confirm your tests fail, then swap them back.
3. Implement the serializer and deserializer, make the deserializer iterative, and round-trip 2,000 random trees.
4. Run every recursive tree function you own on a 100,000-node chain and replace any that crash.
5. Solve one top-down problem, such as root-to-leaf path sums, carrying state on the stack.
6. Extend the walker to an N-ary tree and use it to print a real directory listing.