DSA Traversals

Pre-order Traversal

The query hits at n = 10⁵ nodes: persist the UI tree to disk so a cold start rebuilds the same shape. The serializer must write each parent before either child, or reconstruction loses which subtree owns which leaf.

is that walk: Root → Left → Right. Its guarantee is structural timing, not key order.

Algorithm journey

Need parent first?

Create, serialize, announce, or clone before children.

Emit root, then finish left, then finish right.

Stack detail

Iterative: push right before left so left runs first.

Add null markers or sizes if rebuild must be exact.

What actually happens

Naive idea: dump nodes in any DFS order and hope a loader can rebuild. Without root-first timing (and usually null markers), left/right ambiguity returns.

Better idea: emit the node immediately, then recurse left, then right. The makes induction easy: each call finishes one whole subtree starting with its root.

The improved design still fails on cycles (need a visited set), on recursive chains of length 10⁵ (prefer an explicit stack), and if iterative code pushes left before right (LIFO reverses sibling order).

Invariant / guarantee

For every subtree root x, x appears in the output before every descendant of x. Each node is emitted exactly once. Pre-order does not guarantee sorted keys unless a BST invariant also holds (and even then in-order is the sorted walk).

How to choose pre-order

1. Must the parent run first? Serialization, cloning, top-down propagation: yes. Bottom-up aggregates: use post-order.

2. Need sorted BST keys? Use in-order, not pre-order.

3. Depth untrusted? Prefer the iterative stack form; mark the push-right-first detail in a comment.

Quantitative check

Time is always Θ(n): every node once. Auxiliary stack is Θ(h). At n = 10⁵ balanced, h ≈ 16; skewed, h = 10⁵ and recursive pre-order can overflow before writing the first deep leaf's siblings.

Read the order before writing code

A is the root; B and C are its children. B has D and E. C has F and G.

Output: A, B, D, E, C, F, G

The recursive promise

A call on node x emits every node in x's subtree exactly once, starting with x. A call on null emits nothing. The parent may therefore treat each child call as one complete subtree operation.

Build and traverse a tree

Build a tree, then start pre-order to see the root-first path. Try an empty tree, a chain, and a branching tree.

Build a tree and click Play!

Result:

Empty Tree

What the stack is remembering

Step through suspended recursive calls, then switch to the explicit stack. The output is identical; only the owner of the bookkeeping changes.

Frames, continuations, and output

Follow the same pre-order contract implemented by the language call stack or by an explicit stack.

Step 1 of 43

Ready to call walk(A)

The output and the language call stack both start empty.

Stack (top first)

empty

Output prefix

Nothing visited yet

Invariant: Every emitted node appears before every node in either of its subtrees.

Timeline

Recursive implementation

The visit happens immediately after the null guard. Returning a list makes the example testable; production code can replace the append with any visitor action.

Python

python

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


def preorder(root):
    result = []

    def walk(node):
        if node is None:          # empty-subtree contract
            return
        result.append(node.value) # root
        walk(node.left)           # complete left subtree
        walk(node.right)          # complete right subtree

    walk(root)
    return result


root = Node(1, Node(2, Node(4), Node(5)), Node(3))
print(preorder(root))  # [1, 2, 4, 5, 3]

Java

java

import java.util.ArrayList;
import java.util.List;

public class PreorderRecursive {
    static class Node {
        int value;
        Node left, right;

        Node(int value) { this.value = value; }
        Node(int value, Node left, Node right) {
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    static List<Integer> preorder(Node root) {
        List<Integer> result = new ArrayList<>();
        walk(root, result);
        return result;
    }

    static void walk(Node node, List<Integer> result) {
        if (node == null) return;  // empty-subtree contract
        result.add(node.value);    // root
        walk(node.left, result);   // complete left subtree
        walk(node.right, result);  // complete right subtree
    }

    public static void main(String[] args) {
        Node root = new Node(1,
            new Node(2, new Node(4), new Node(5)),
            new Node(3));
        System.out.println(preorder(root)); // [1, 2, 4, 5, 3]
    }
}

Iterative implementation

A LIFO stack reverses insertion order, so push the right child first. That small detail is the most common pre-order bug.

Python

python

def preorder_iterative(root):
    if root is None:
        return []

    result = []
    stack = [root]

    while stack:
        node = stack.pop()
        result.append(node.value)

        # Right first, so left is processed first.
        if node.right is not None:
            stack.append(node.right)
        if node.left is not None:
            stack.append(node.left)

    return result

Java

java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

final class PreorderIterative {
    static final class Node {
        final int value;
        Node left, right;

        Node(int value) {
            this.value = value;
        }
    }

    static List<Integer> traverse(Node root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;

        Deque<Node> stack = new ArrayDeque<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            Node node = stack.pop();
            result.add(node.value);

            // ArrayDeque rejects null, so guard each child.
            if (node.right != null) stack.push(node.right);
            if (node.left != null) stack.push(node.left);
        }
        return result;
    }
}

Why it is correct

Base case

An empty subtree contains no nodes, so returning without output is correct.

Inductive step

Emit the root, then rely on the same promise for the smaller left and right subtrees.

Exactly once

Every non-root node is reached through its one parent edge; no call schedules it twice.

Complexity and shape

Pre-order time and space complexity by tree shape
Measure	Balanced tree	Skewed tree	Reason
Time	Θ(n)	Θ(n)	Every node is visited once.
Auxiliary stack	Θ(log n)	Θ(n)	Depth-first state follows tree height h.
Returned output	Θ(n)	Θ(n)	Storing results is separate from traversal workspace.

Recursion risk: a chain-shaped tree creates n nested calls and may overflow the runtime call stack. The iterative version moves that state to heap-backed storage and uses O(h) entries in the worst case.

When root-first order is useful

Serialization

Write a node before its children; include null markers if the exact shape must be recoverable.

Hierarchical UI

Render a parent heading or folder before rendering its descendants.

Prefix expressions

An expression-tree operator appears before its operand subtrees.

Clone or transform

Create the destination parent before attaching recursively transformed children.

Edge cases and failure modes

Empty tree: return an empty result; do not push a null root into Java's ArrayDeque.
Duplicate values: values need not be unique; traversal follows node identity and edges.
Not a tree: cycles or shared children require a visited set, or the walk may repeat forever.
Mutation: changing child links during a visit can skip or repeat work; define snapshot semantics first.

Exercises

For root A with children B,C and grandchildren D,E under B and F,G under C, write the pre-order sequence. Which nodes must appear before E?
Show a counterexample where pre-order of a BST is not sorted. Which traversal would you use instead for sorted keys?
Fix an iterative pre-order that pushes left then right. What sibling order does it emit, and why?

Primary sources

Cormen et al., Introduction to Algorithms (CLRS): tree walks and preorder as a DFS finishing pattern on trees.
Knuth, TAOCP Vol. 1: preorder, inorder, postorder nomenclature and stack simulations.
LeetCode 297 (Serialize and Deserialize Binary Tree): pre-order with null markers as a classic shape contract.