Data Structures & AlgorithmsTree Traversals

Tree Traversals — Inorder, Preorder, Postorder

LevelIntermediate

Duration75 mins

TopicTree Traversals

2 / 5

Preorder Traversal — Root → Left → Right

The "Self-First" Traversal

Imagine you're a project manager documenting your organization's structure. You write down your own name first, then recursively document everyone in your left division, then everyone in your right division. This "self-first" approach—process yourself before delegating to subordinates—captures the essence of preorder traversal.

Preorder traversal visits nodes in the order: Root → Left → Right. The current node is always processed before either of its subtrees. This makes preorder the natural choice whenever you need to record or process a node before dealing with its descendants—whether copying a tree, serializing data, or exploring a file system.

What You Will Learn

By the end of this page, you will master preorder traversal—understanding exactly how it works, implementing it both recursively and iteratively, tracing its execution step-by-step, and recognizing when preorder is the right choice for a problem. You'll see why "visit first, explore later" is a powerful pattern.

The Preorder Algorithm Defined

Preorder traversal follows a simple, elegant rule:

For each node, do these three things in this exact order:

Visit the current node (process it, record it, print it—whatever operation you need)
Traverse the left subtree (recursively apply the same rule)
Traverse the right subtree (recursively apply the same rule)

The key insight: the root of any subtree is always visited before any nodes in that subtree. This "parent-before-children" property makes preorder ideal for operations that need to establish something at a node before processing its descendants.

preorder-definition.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
PREORDER TRAVERSAL ALGORITHM
═══════════════════════════════════════════════════════════════
 
    Input:  Root node of a binary tree (or null)
    Output: Sequence of node values in preorder
 
    Procedure PREORDER(node):
        1. If node is null:
              Return (base case: nothing to visit)
        
        2. VISIT(node)           ← Process current node FIRST
        
        3. PREORDER(node.left)   ← Then traverse left subtree
        
        4. PREORDER(node.right)  ← Then traverse right subtree
 
═══════════════════════════════════════════════════════════════
 
    Mnemonic: "VLR" — Visit, Left, Right
    
    The V (Visit) comes FIRST, hence "PRE-order"
    (as in "prefix" — the root goes at the front)

Why "Preorder"?

The name comes from the position of the Visit operation: BEFORE (pre-) the recursive traversals of subtrees. Compare this to inorder (visit in the middle) and postorder (visit after). The naming precisely describes when the root is processed relative to its subtrees.

Recursive Implementation

The recursive implementation of preorder traversal is remarkably simple—it directly translates the algorithm definition into code. This simplicity is not accidental: it reflects the deep connection between the recursive structure of trees and recursive algorithms.

Let's implement preorder traversal with full type safety and understand every line:

preorder-recursive.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
/**
 * Binary tree node definition
 */
interface TreeNode<T> {
    value: T;
    left: TreeNode<T> | null;
    right: TreeNode<T> | null;
}
 
/**
 * Preorder traversal - recursive implementation
 * 
 * Time Complexity:  O(n) - visits each node exactly once
 * Space Complexity: O(h) - recursive call stack depth equals tree height
 *                   Best case (balanced): O(log n)
 *                   Worst case (skewed):  O(n)
 * 
 * @param root - The root of the tree (or subtree)
 * @param result - Array to collect values (accumulator pattern)
 * @returns Array of values in preorder sequence
 */
function preorderTraversal<T>(
    root: TreeNode<T> | null,
    result: T[] = []
): T[] {
    // Base case: empty tree/subtree
    if (root === null) {
        return result;
    }
    
    // Step 1: VISIT - Process current node first (the "PRE" in preorder)
    result.push(root.value);
    
    // Step 2: LEFT - Recursively traverse left subtree
    preorderTraversal(root.left, result);
    
    // Step 3: RIGHT - Recursively traverse right subtree
    preorderTraversal(root.right, result);
    
    return result;
}
 
// ─────────────────────────────────────────────────────────────
// Example usage
// ─────────────────────────────────────────────────────────────
 
/*
 * Tree structure:
 *         1
 *        / \
 *       2   3
 *      / \
 *     4   5
 */
 
const tree: TreeNode<number> = {
    value: 1,
    left: {
        value: 2,
        left: { value: 4, left: null, right: null },
        right: { value: 5, left: null, right: null },
    },
    right: {
        value: 3,
        left: null,
        right: null,
    },
};
 
console.log(preorderTraversal(tree));
// Output: [1, 2, 4, 5, 3]
// Explanation: Visit 1, then entire left subtree [2,4,5], then right subtree [3]

Understanding the elegance:

Notice how the three lines after the base case directly correspond to "Visit, Left, Right":

result.push(root.value) — Visit
preorderTraversal(root.left, result) — Left subtree
preorderTraversal(root.right, result) — Right subtree

The order of these three statements is the ONLY thing that distinguishes preorder from inorder and postorder. This is extraordinary—such a tiny code change, yet fundamentally different traversal orders.

Step-by-Step Execution Trace

To truly understand preorder traversal, let's trace through a complete example. We'll follow the call stack and see exactly when each node is visited.

Sample tree:

preorder-trace.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
PREORDER TRAVERSAL EXECUTION TRACE
═══════════════════════════════════════════════════════════════════════════
 
Tree:           A
               / \
              B   C
             / \   \
            D   E   F
 
═══════════════════════════════════════════════════════════════════════════
Step  Call Stack          Action                    Result So Far
═══════════════════════════════════════════════════════════════════════════
 1    preorder(A)         VISIT A                   [A]
 2    preorder(A)         Call preorder(B)          [A]
 3    └─preorder(B)       VISIT B                   [A, B]
 4    └─preorder(B)       Call preorder(D)          [A, B]
 5      └─preorder(D)     VISIT D                   [A, B, D]
 6      └─preorder(D)     Call preorder(null)       [A, B, D]
 7        └─null          Return (base case)        [A, B, D]
 8      └─preorder(D)     Call preorder(null)       [A, B, D]
 9        └─null          Return (base case)        [A, B, D]
10      └─preorder(D)     Return                    [A, B, D]
11    └─preorder(B)       Call preorder(E)          [A, B, D]
12      └─preorder(E)     VISIT E                   [A, B, D, E]
13      └─preorder(E)     Call preorder(null)       [A, B, D, E]
14        └─null          Return (base case)        [A, B, D, E]
15      └─preorder(E)     Call preorder(null)       [A, B, D, E]
16        └─null          Return (base case)        [A, B, D, E]
17      └─preorder(E)     Return                    [A, B, D, E]
18    └─preorder(B)       Return                    [A, B, D, E]
19    preorder(A)         Call preorder(C)          [A, B, D, E]
20    └─preorder(C)       VISIT C                   [A, B, D, E, C]
21    └─preorder(C)       Call preorder(null)       [A, B, D, E, C]
22      └─null            Return (base case)        [A, B, D, E, C]
23    └─preorder(C)       Call preorder(F)          [A, B, D, E, C]
24      └─preorder(F)     VISIT F                   [A, B, D, E, C, F]
25      └─preorder(F)     Call preorder(null)       [A, B, D, E, C, F]
26        └─null          Return (base case)        [A, B, D, E, C, F]
27      └─preorder(F)     Call preorder(null)       [A, B, D, E, C, F]
28        └─null          Return (base case)        [A, B, D, E, C, F]
29      └─preorder(F)     Return                    [A, B, D, E, C, F]
30    └─preorder(C)       Return                    [A, B, D, E, C, F]
31    preorder(A)         Return                    [A, B, D, E, C, F]
═══════════════════════════════════════════════════════════════════════════
 
FINAL RESULT: [A, B, D, E, C, F]
 
KEY OBSERVATIONS:
• Each node is visited BEFORE its children (preorder property)
• Left subtree [B, D, E] is fully processed before right subtree [C, F]
• Maximum stack depth = 3 (height of tree) at steps 5-9 and 24-28
• Total VISIT operations = 6 (one per node)
• Total function calls = 13 (6 nodes + 7 null checks)

Tracing Builds Intuition

Working through execution traces by hand is one of the best ways to internalize how recursive algorithms work. Practice tracing on paper until you can "see" the traversal happening in your mind without writing it out. This skill transfers to all recursive tree problems.

Iterative Implementation with Explicit Stack

While recursion is elegant, it has limitations: primarily stack overflow for very deep trees. The iterative approach uses an explicit stack data structure instead of the call stack, giving us control over memory usage and avoiding recursion limits.

The key insight: every recursive algorithm can be converted to iteration using an explicit stack. For preorder, the conversion is particularly clean because of how the algorithm processes nodes.

preorder-iterative.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
/**
 * Preorder traversal - iterative implementation using explicit stack
 * 
 * Time Complexity:  O(n) - visits each node exactly once
 * Space Complexity: O(h) - explicit stack depth equals tree height
 *                   (same as recursive, but avoids call stack limits)
 * 
 * Key Insight: Push right child first, then left, so left is processed first
 *              (LIFO - Last In First Out)
 */
function preorderIterative<T>(root: TreeNode<T> | null): T[] {
    const result: T[] = [];
    
    // Handle empty tree
    if (root === null) {
        return result;
    }
    
    // Stack to hold nodes for processing
    // Initialize with root node
    const stack: TreeNode<T>[] = [root];
    
    // Process until stack is empty
    while (stack.length > 0) {
        // Pop the top node - this will be visited NOW (preorder: visit first)
        const current = stack.pop()!;
        
        // VISIT: Process the current node
        result.push(current.value);
        
        // Push children onto stack
        // IMPORTANT: Push RIGHT first, then LEFT
        // Because stack is LIFO, left will be popped (processed) first
        
        if (current.right !== null) {
            stack.push(current.right);  // Right goes in first (popped second)
        }
        
        if (current.left !== null) {
            stack.push(current.left);   // Left goes in second (popped first)
        }
    }
    
    return result;
}
 
// ─────────────────────────────────────────────────────────────
// Stack state visualization for the example tree
// ─────────────────────────────────────────────────────────────
 
/*
 * Tree:        1
 *             / \
 *            2   3
 *           / \
 *          4   5
 *
 * Step-by-step stack states:
 * 
 * Initial:    Stack: [1]           Result: []
 * Pop 1:      Stack: [3, 2]        Result: [1]      (pushed 3 then 2)
 * Pop 2:      Stack: [3, 5, 4]     Result: [1, 2]   (pushed 5 then 4)
 * Pop 4:      Stack: [3, 5]        Result: [1, 2, 4] (4 has no children)
 * Pop 5:      Stack: [3]           Result: [1, 2, 4, 5] (5 has no children)
 * Pop 3:      Stack: []            Result: [1, 2, 4, 5, 3] (3 has no children)
 * 
 * Final:      Result: [1, 2, 4, 5, 3] ✓
 */

Why Push Right Before Left?

This is a common source of bugs! Since a stack is Last-In-First-Out, we must push the right child BEFORE the left child. This ensures the left child is on TOP of the stack and gets popped (processed) first. If you push left before right, you'll get a right-then-left traversal—which is NOT preorder.

Recursive vs Iterative: When to Use Each

Both implementations produce identical results. The choice depends on your context:

Recursive vs Iterative Preorder Traversal
Aspect	Recursive	Iterative
Code Clarity	More intuitive, directly maps to algorithm	More verbose, explicit stack management
Space	Uses call stack (O(h))	Uses explicit stack (O(h))
Stack Limits	Subject to recursion depth limits	Only limited by available memory
Performance	Function call overhead	Slightly faster (no call overhead)
Debugging	Harder to inspect call stack	Easier to inspect explicit stack
Interview Preference	Often expected first	Good to know as follow-up
Production Code	Usually fine unless tree is very deep	Preferred for unknown/large trees

Use Recursive When

•Tree height is bounded (e.g., balanced trees)
•Code readability is priority
•You're in an interview (cleaner to write)
•The problem naturally has recursive structure
•Language has tail-call optimization

Use Iterative When

•Tree depth is unknown or potentially huge
•You need to avoid stack overflow
•Performance is critical (avoid function overhead)
•You need fine-grained control over traversal
•Language has strict recursion limits (e.g., Python's 1000)

Interview Tip

In interviews, start with the recursive solution—it's faster to write and easier to verify. If the interviewer asks about stack overflow concerns or wants to see the iterative version, you can then present it as an optimization. This shows both depth of knowledge and practical judgment.

Preorder Properties and Invariants

Understanding the mathematical properties of preorder traversal helps you recognize when it's the right tool and reason about correctness:

Property 1: Root Primacy The root of any subtree always appears before all nodes in that subtree. This means:

The FIRST element in any preorder traversal is always the tree's root
For any subtree starting at position i, position i contains that subtree's root

Property 2: Left-Before-Right All nodes in the left subtree appear before all nodes in the right subtree. Combined with Property 1:

Preorder = [Root] + [Preorder of Left Subtree] + [Preorder of Right Subtree]

Property 3: Ancestor Precedence If node A is an ancestor of node B, then A appears before B in preorder. This property is critical for many algorithms.

preorder-structure.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
PREORDER DECOMPOSITION PROPERTY
═══════════════════════════════════════════════════════════════════════════
 
For any binary tree T with root R, left subtree L, and right subtree R:
 
    Preorder(T) = [R] ⊕ Preorder(L) ⊕ Preorder(R)
 
    where ⊕ denotes concatenation
 
═══════════════════════════════════════════════════════════════════════════
 
Example:
              1
             / \
            2   3          Preorder of tree rooted at 1:
           / \   \
          4   5   6        = [1] ⊕ Preorder([2,4,5]) ⊕ Preorder([3,6])
                           = [1] ⊕ [2,4,5] ⊕ [3,6]
                           = [1, 2, 4, 5, 3, 6]
 
Implications:
• Given preorder, the first element is ALWAYS the root
• Given preorder + tree structure, you can locate any subtree's preorder
• This property enables tree reconstruction from preorder sequence

Uniqueness Consideration

A preorder sequence alone does NOT uniquely define a binary tree structure. For example, [1,2,3] could be a left-skewed tree (1→2→3), right-skewed (1→3←2), or various other shapes. However, preorder PLUS inorder (or preorder plus structure info) uniquely determines the tree. This is important for tree serialization.

Real-World Applications of Preorder

Preorder traversal isn't just an academic exercise—it's the right tool for many practical problems. Here are common scenarios where preorder is the natural choice:

Application: Tree Serialization

•Problem: Convert a tree to a string/array that can be stored or transmitted
•Why Preorder: Parent must be written before children so structure can be reconstructed
•Example: JSON serialization of tree structures, file system backups
•Key insight: Preorder + null markers is sufficient for unique reconstruction

Application: Tree Copying/Cloning

•Problem: Create a deep copy of a tree
•Why Preorder: Must create parent node before attaching children to it
•Process: Visit node (create copy), recurse left, recurse right
•Key insight: You cannot attach children to a nonexistent parent

Application: File System Traversal

•Problem: List directory structure with proper indentation
•Why Preorder: Print folder name, then its contents
•Example: The tree command in Unix/Windows terminal
•Key insight: You want to see 'Projects/' before seeing 'Projects/src/'

preorder-clone.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Clone a binary tree using preorder traversal
 * 
 * The preorder approach is natural here because:
 * 1. We must CREATE the clone of the current node FIRST
 * 2. Only THEN can we attach cloned children to it
 * 3. This matches preorder: Visit (create) → Left → Right
 */
function cloneTree<T>(root: TreeNode<T> | null): TreeNode<T> | null {
    // Base case: nothing to clone
    if (root === null) {
        return null;
    }
    
    // VISIT: Create clone of current node (preorder - process first!)
    const clonedNode: TreeNode<T> = {
        value: root.value,  // Copy the value
        left: null,
        right: null,
    };
    
    // LEFT: Clone left subtree and attach
    clonedNode.left = cloneTree(root.left);
    
    // RIGHT: Clone right subtree and attach
    clonedNode.right = cloneTree(root.right);
    
    return clonedNode;
}
 
// Note: The node MUST be created before we can attach children to it.
// This is why preorder is the ONLY correct traversal for cloning.
// Inorder or postorder would try to attach children before creating parent!

Prefix Expressions and Expression Trees

One of the most elegant applications of preorder traversal is in expression trees for mathematical expressions. An expression tree represents a calculation where:

Internal nodes are operators (+, -, *, /)
Leaf nodes are operands (numbers or variables)

Preorder traversal of an expression tree produces prefix notation (also called Polish notation), where operators come before their operands. This notation has a remarkable property: no parentheses are needed because the structure is unambiguous.

prefix-expression.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
EXPRESSION TREE EXAMPLE
═══════════════════════════════════════════════════════════════════════════
 
Infix expression (normal math): (3 + 4) * (5 - 2)
 
Expression tree:
                    *
                   / \
                  +   -
                 / \ / \
                3  4 5  2
 
Preorder traversal (prefix notation): * + 3 4 - 5 2
 
═══════════════════════════════════════════════════════════════════════════
 
Reading prefix notation:
• First symbol (*) is the operator
• Next group (+ 3 4) is left operand → evaluates to 7
• Next group (- 5 2) is right operand → evaluates to 3
• Final: 7 * 3 = 21
 
Why prefix is useful:
• No parentheses needed (unambiguous without them)
• Easy to evaluate with a stack
• Used in LISP, Scheme, and other functional languages
• Calculators like HP used a variant (Reverse Polish / postfix)

prefix-from-tree.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
 * Expression tree node
 */
interface ExprNode {
    value: string;  // Operator (+, -, *, /) or operand (number)
    left: ExprNode | null;
    right: ExprNode | null;
}
 
/**
 * Generate prefix notation from expression tree
 * Uses preorder traversal: operator BEFORE operands
 */
function toPrefix(root: ExprNode | null): string {
    if (root === null) {
        return "";
    }
    
    // Leaf node (operand)
    if (root.left === null && root.right === null) {
        return root.value;
    }
    
    // Internal node (operator) - preorder: visit, left, right
    const operator = root.value;
    const leftExpr = toPrefix(root.left);
    const rightExpr = toPrefix(root.right);
    
    return `${operator} ${leftExpr} ${rightExpr}`;
}
 
// Example: (3 + 4) * (5 - 2)
const expressionTree: ExprNode = {
    value: "*",
    left: {
        value: "+",
        left: { value: "3", left: null, right: null },
        right: { value: "4", left: null, right: null },
    },
    right: {
        value: "-",
        left: { value: "5", left: null, right: null },
        right: { value: "2", left: null, right: null },
    },
};
 
console.log(toPrefix(expressionTree));
// Output: "* + 3 4 - 5 2"

Common Preorder Patterns

Preorder traversal appears in many problem patterns. Recognizing these patterns helps you quickly identify when preorder is the right approach:

preorder-path-pattern.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * Pattern: Tracking path from root to current node
 * 
 * Many tree problems need to know the path from root to current node.
 * Preorder is natural because we can BUILD the path as we descend.
 */
function printRootToLeafPaths<T>(
    root: TreeNode<T> | null,
    path: T[] = []
): void {
    if (root === null) {
        return;
    }
    
    // VISIT: Add current node to path (preorder - before children)
    path.push(root.value);
    
    // If leaf node, print the complete path
    if (root.left === null && root.right === null) {
        console.log("Path:", path.join(" → "));
    }
    
    // Recurse on children
    printRootToLeafPaths(root.left, path);
    printRootToLeafPaths(root.right, path);
    
    // Backtrack: remove current node when returning
    path.pop();
}
 
/*
 * Tree:        1
 *             / \
 *            2   3
 *           / \
 *          4   5
 *
 * Output:
 * Path: 1 → 2 → 4
 * Path: 1 → 2 → 5
 * Path: 1 → 3
 */

preorder-depth-pattern.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * Pattern: Track depth/level during traversal
 * 
 * Preorder lets us pass down information (like depth) to children.
 * This "top-down" information flow matches preorder naturally.
 */
function printNodesWithDepth<T>(
    root: TreeNode<T> | null,
    depth: number = 0
): void {
    if (root === null) {
        return;
    }
    
    // VISIT: Print node with its depth
    const indent = "  ".repeat(depth);
    console.log(`${indent}Level ${depth}: ${root.value}`);
    
    // Pass depth + 1 to children
    printNodesWithDepth(root.left, depth + 1);
    printNodesWithDepth(root.right, depth + 1);
}
 
/*
 * Tree:        A
 *             / \
 *            B   C
 *           /
 *          D
 *
 * Output:
 * Level 0: A
 *   Level 1: B
 *     Level 2: D
 *   Level 1: C
 */

Top-Down vs Bottom-Up

Preorder is ideal for TOP-DOWN information flow—passing data from parent to children (like depth, path, or constraints). In contrast, postorder is ideal for BOTTOM-UP flow—computing values from children and passing up to parents (like height or subtree sums). Recognize which direction your information flows to choose the right traversal.

Summary: Mastering Preorder Traversal

You've now gained comprehensive understanding of preorder traversal. Let's consolidate the key points:

Key Takeaways

•Preorder = Root → Left → Right — Visit current node BEFORE processing children.
•"PRE" means process first — The root comes at the front, like a prefix.
•Recursive implementation is elegant — Three lines after base case: visit, left, right.
•Iterative uses stack with reversed push — Push right before left so left pops first.
•Time O(n), Space O(h) — Same complexity for both recursive and iterative.
•First element is always root — Critical property for reconstruction algorithms.
•Use for top-down problems — When parent info must be processed before children.
•Classic applications — Tree cloning, serialization, prefix expressions, directory listing.

When to choose preorder:

You need to process/create a node before its descendants
You're passing information DOWN the tree (top-down)
You need the root of each subtree identified first
The problem involves creating or copying tree structure

What's next:

Now that you've mastered preorder (Root → Left → Right), we'll explore Inorder Traversal (Left → Root → Right). You'll see how moving the visit operation to the middle creates fundamentally different behavior—particularly powerful for Binary Search Trees where inorder produces sorted output.

Preorder Mastery Complete

You now understand preorder traversal deeply—from algorithm definition through implementation to real-world applications. You can implement it recursively and iteratively, trace its execution, and recognize when it's the right tool. This is the first of three core traversals that form the foundation of tree algorithm mastery.

2 / 5

Loading learning content...

Data Structures & AlgorithmsTree Traversals

Tree Traversals — Inorder, Preorder, Postorder

LevelIntermediate

Duration75 mins

TopicTree Traversals

2 / 5

Preorder Traversal — Root → Left → Right

The "Self-First" Traversal

What You Will Learn

The Preorder Algorithm Defined

Preorder traversal follows a simple, elegant rule:

For each node, do these three things in this exact order:

Visit the current node (process it, record it, print it—whatever operation you need)
Traverse the left subtree (recursively apply the same rule)
Traverse the right subtree (recursively apply the same rule)

preorder-definition.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
PREORDER TRAVERSAL ALGORITHM
═══════════════════════════════════════════════════════════════
 
    Input:  Root node of a binary tree (or null)
    Output: Sequence of node values in preorder
 
    Procedure PREORDER(node):
        1. If node is null:
              Return (base case: nothing to visit)
        
        2. VISIT(node)           ← Process current node FIRST
        
        3. PREORDER(node.left)   ← Then traverse left subtree
        
        4. PREORDER(node.right)  ← Then traverse right subtree
 
═══════════════════════════════════════════════════════════════
 
    Mnemonic: "VLR" — Visit, Left, Right
    
    The V (Visit) comes FIRST, hence "PRE-order"
    (as in "prefix" — the root goes at the front)

Why "Preorder"?

Recursive Implementation

Let's implement preorder traversal with full type safety and understand every line:

preorder-recursive.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
/**
 * Binary tree node definition
 */
interface TreeNode<T> {
    value: T;
    left: TreeNode<T> | null;
    right: TreeNode<T> | null;
}
 
/**
 * Preorder traversal - recursive implementation
 * 
 * Time Complexity:  O(n) - visits each node exactly once
 * Space Complexity: O(h) - recursive call stack depth equals tree height
 *                   Best case (balanced): O(log n)
 *                   Worst case (skewed):  O(n)
 * 
 * @param root - The root of the tree (or subtree)
 * @param result - Array to collect values (accumulator pattern)
 * @returns Array of values in preorder sequence
 */
function preorderTraversal<T>(
    root: TreeNode<T> | null,
    result: T[] = []
): T[] {
    // Base case: empty tree/subtree
    if (root === null) {
        return result;
    }
    
    // Step 1: VISIT - Process current node first (the "PRE" in preorder)
    result.push(root.value);
    
    // Step 2: LEFT - Recursively traverse left subtree
    preorderTraversal(root.left, result);
    
    // Step 3: RIGHT - Recursively traverse right subtree
    preorderTraversal(root.right, result);
    
    return result;
}
 
// ─────────────────────────────────────────────────────────────
// Example usage
// ─────────────────────────────────────────────────────────────
 
/*
 * Tree structure:
 *         1
 *        / \
 *       2   3
 *      / \
 *     4   5
 */
 
const tree: TreeNode<number> = {
    value: 1,
    left: {
        value: 2,
        left: { value: 4, left: null, right: null },
        right: { value: 5, left: null, right: null },
    },
    right: {
        value: 3,
        left: null,
        right: null,
    },
};
 
console.log(preorderTraversal(tree));
// Output: [1, 2, 4, 5, 3]
// Explanation: Visit 1, then entire left subtree [2,4,5], then right subtree [3]

Understanding the elegance:

Notice how the three lines after the base case directly correspond to "Visit, Left, Right":

result.push(root.value) — Visit
preorderTraversal(root.left, result) — Left subtree
preorderTraversal(root.right, result) — Right subtree

Step-by-Step Execution Trace

To truly understand preorder traversal, let's trace through a complete example. We'll follow the call stack and see exactly when each node is visited.

Sample tree:

preorder-trace.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
PREORDER TRAVERSAL EXECUTION TRACE
═══════════════════════════════════════════════════════════════════════════
 
Tree:           A
               / \
              B   C
             / \   \
            D   E   F
 
═══════════════════════════════════════════════════════════════════════════
Step  Call Stack          Action                    Result So Far
═══════════════════════════════════════════════════════════════════════════
 1    preorder(A)         VISIT A                   [A]
 2    preorder(A)         Call preorder(B)          [A]
 3    └─preorder(B)       VISIT B                   [A, B]
 4    └─preorder(B)       Call preorder(D)          [A, B]
 5      └─preorder(D)     VISIT D                   [A, B, D]
 6      └─preorder(D)     Call preorder(null)       [A, B, D]
 7        └─null          Return (base case)        [A, B, D]
 8      └─preorder(D)     Call preorder(null)       [A, B, D]
 9        └─null          Return (base case)        [A, B, D]
10      └─preorder(D)     Return                    [A, B, D]
11    └─preorder(B)       Call preorder(E)          [A, B, D]
12      └─preorder(E)     VISIT E                   [A, B, D, E]
13      └─preorder(E)     Call preorder(null)       [A, B, D, E]
14        └─null          Return (base case)        [A, B, D, E]
15      └─preorder(E)     Call preorder(null)       [A, B, D, E]
16        └─null          Return (base case)        [A, B, D, E]
17      └─preorder(E)     Return                    [A, B, D, E]
18    └─preorder(B)       Return                    [A, B, D, E]
19    preorder(A)         Call preorder(C)          [A, B, D, E]
20    └─preorder(C)       VISIT C                   [A, B, D, E, C]
21    └─preorder(C)       Call preorder(null)       [A, B, D, E, C]
22      └─null            Return (base case)        [A, B, D, E, C]
23    └─preorder(C)       Call preorder(F)          [A, B, D, E, C]
24      └─preorder(F)     VISIT F                   [A, B, D, E, C, F]
25      └─preorder(F)     Call preorder(null)       [A, B, D, E, C, F]
26        └─null          Return (base case)        [A, B, D, E, C, F]
27      └─preorder(F)     Call preorder(null)       [A, B, D, E, C, F]
28        └─null          Return (base case)        [A, B, D, E, C, F]
29      └─preorder(F)     Return                    [A, B, D, E, C, F]
30    └─preorder(C)       Return                    [A, B, D, E, C, F]
31    preorder(A)         Return                    [A, B, D, E, C, F]
═══════════════════════════════════════════════════════════════════════════
 
FINAL RESULT: [A, B, D, E, C, F]
 
KEY OBSERVATIONS:
• Each node is visited BEFORE its children (preorder property)
• Left subtree [B, D, E] is fully processed before right subtree [C, F]
• Maximum stack depth = 3 (height of tree) at steps 5-9 and 24-28
• Total VISIT operations = 6 (one per node)
• Total function calls = 13 (6 nodes + 7 null checks)

Tracing Builds Intuition

Iterative Implementation with Explicit Stack

The key insight: every recursive algorithm can be converted to iteration using an explicit stack. For preorder, the conversion is particularly clean because of how the algorithm processes nodes.

preorder-iterative.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
/**
 * Preorder traversal - iterative implementation using explicit stack
 * 
 * Time Complexity:  O(n) - visits each node exactly once
 * Space Complexity: O(h) - explicit stack depth equals tree height
 *                   (same as recursive, but avoids call stack limits)
 * 
 * Key Insight: Push right child first, then left, so left is processed first
 *              (LIFO - Last In First Out)
 */
function preorderIterative<T>(root: TreeNode<T> | null): T[] {
    const result: T[] = [];
    
    // Handle empty tree
    if (root === null) {
        return result;
    }
    
    // Stack to hold nodes for processing
    // Initialize with root node
    const stack: TreeNode<T>[] = [root];
    
    // Process until stack is empty
    while (stack.length > 0) {
        // Pop the top node - this will be visited NOW (preorder: visit first)
        const current = stack.pop()!;
        
        // VISIT: Process the current node
        result.push(current.value);
        
        // Push children onto stack
        // IMPORTANT: Push RIGHT first, then LEFT
        // Because stack is LIFO, left will be popped (processed) first
        
        if (current.right !== null) {
            stack.push(current.right);  // Right goes in first (popped second)
        }
        
        if (current.left !== null) {
            stack.push(current.left);   // Left goes in second (popped first)
        }
    }
    
    return result;
}
 
// ─────────────────────────────────────────────────────────────
// Stack state visualization for the example tree
// ─────────────────────────────────────────────────────────────
 
/*
 * Tree:        1
 *             / \
 *            2   3
 *           / \
 *          4   5
 *
 * Step-by-step stack states:
 * 
 * Initial:    Stack: [1]           Result: []
 * Pop 1:      Stack: [3, 2]        Result: [1]      (pushed 3 then 2)
 * Pop 2:      Stack: [3, 5, 4]     Result: [1, 2]   (pushed 5 then 4)
 * Pop 4:      Stack: [3, 5]        Result: [1, 2, 4] (4 has no children)
 * Pop 5:      Stack: [3]           Result: [1, 2, 4, 5] (5 has no children)
 * Pop 3:      Stack: []            Result: [1, 2, 4, 5, 3] (3 has no children)
 * 
 * Final:      Result: [1, 2, 4, 5, 3] ✓
 */

Why Push Right Before Left?

Recursive vs Iterative: When to Use Each

Both implementations produce identical results. The choice depends on your context:

Recursive vs Iterative Preorder Traversal
Aspect	Recursive	Iterative
Code Clarity	More intuitive, directly maps to algorithm	More verbose, explicit stack management
Space	Uses call stack (O(h))	Uses explicit stack (O(h))
Stack Limits	Subject to recursion depth limits	Only limited by available memory
Performance	Function call overhead	Slightly faster (no call overhead)
Debugging	Harder to inspect call stack	Easier to inspect explicit stack
Interview Preference	Often expected first	Good to know as follow-up
Production Code	Usually fine unless tree is very deep	Preferred for unknown/large trees

Use Recursive When

•Tree height is bounded (e.g., balanced trees)
•Code readability is priority
•You're in an interview (cleaner to write)
•The problem naturally has recursive structure
•Language has tail-call optimization

Use Iterative When

•Tree depth is unknown or potentially huge
•You need to avoid stack overflow
•Performance is critical (avoid function overhead)
•You need fine-grained control over traversal
•Language has strict recursion limits (e.g., Python's 1000)

Interview Tip

Preorder Properties and Invariants

Understanding the mathematical properties of preorder traversal helps you recognize when it's the right tool and reason about correctness:

Property 1: Root Primacy The root of any subtree always appears before all nodes in that subtree. This means:

The FIRST element in any preorder traversal is always the tree's root
For any subtree starting at position i, position i contains that subtree's root

Property 2: Left-Before-Right All nodes in the left subtree appear before all nodes in the right subtree. Combined with Property 1:

Preorder = [Root] + [Preorder of Left Subtree] + [Preorder of Right Subtree]

Property 3: Ancestor Precedence If node A is an ancestor of node B, then A appears before B in preorder. This property is critical for many algorithms.

preorder-structure.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
PREORDER DECOMPOSITION PROPERTY
═══════════════════════════════════════════════════════════════════════════
 
For any binary tree T with root R, left subtree L, and right subtree R:
 
    Preorder(T) = [R] ⊕ Preorder(L) ⊕ Preorder(R)
 
    where ⊕ denotes concatenation
 
═══════════════════════════════════════════════════════════════════════════
 
Example:
              1
             / \
            2   3          Preorder of tree rooted at 1:
           / \   \
          4   5   6        = [1] ⊕ Preorder([2,4,5]) ⊕ Preorder([3,6])
                           = [1] ⊕ [2,4,5] ⊕ [3,6]
                           = [1, 2, 4, 5, 3, 6]
 
Implications:
• Given preorder, the first element is ALWAYS the root
• Given preorder + tree structure, you can locate any subtree's preorder
• This property enables tree reconstruction from preorder sequence

Uniqueness Consideration

Real-World Applications of Preorder

Preorder traversal isn't just an academic exercise—it's the right tool for many practical problems. Here are common scenarios where preorder is the natural choice:

Application: Tree Serialization

•Problem: Convert a tree to a string/array that can be stored or transmitted
•Why Preorder: Parent must be written before children so structure can be reconstructed
•Example: JSON serialization of tree structures, file system backups
•Key insight: Preorder + null markers is sufficient for unique reconstruction

Application: Tree Copying/Cloning

•Problem: Create a deep copy of a tree
•Why Preorder: Must create parent node before attaching children to it
•Process: Visit node (create copy), recurse left, recurse right
•Key insight: You cannot attach children to a nonexistent parent

Application: File System Traversal

•Problem: List directory structure with proper indentation
•Why Preorder: Print folder name, then its contents
•Example: The tree command in Unix/Windows terminal
•Key insight: You want to see 'Projects/' before seeing 'Projects/src/'

preorder-clone.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Clone a binary tree using preorder traversal
 * 
 * The preorder approach is natural here because:
 * 1. We must CREATE the clone of the current node FIRST
 * 2. Only THEN can we attach cloned children to it
 * 3. This matches preorder: Visit (create) → Left → Right
 */
function cloneTree<T>(root: TreeNode<T> | null): TreeNode<T> | null {
    // Base case: nothing to clone
    if (root === null) {
        return null;
    }
    
    // VISIT: Create clone of current node (preorder - process first!)
    const clonedNode: TreeNode<T> = {
        value: root.value,  // Copy the value
        left: null,
        right: null,
    };
    
    // LEFT: Clone left subtree and attach
    clonedNode.left = cloneTree(root.left);
    
    // RIGHT: Clone right subtree and attach
    clonedNode.right = cloneTree(root.right);
    
    return clonedNode;
}
 
// Note: The node MUST be created before we can attach children to it.
// This is why preorder is the ONLY correct traversal for cloning.
// Inorder or postorder would try to attach children before creating parent!

Prefix Expressions and Expression Trees

One of the most elegant applications of preorder traversal is in expression trees for mathematical expressions. An expression tree represents a calculation where:

Internal nodes are operators (+, -, *, /)
Leaf nodes are operands (numbers or variables)

prefix-expression.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
EXPRESSION TREE EXAMPLE
═══════════════════════════════════════════════════════════════════════════
 
Infix expression (normal math): (3 + 4) * (5 - 2)
 
Expression tree:
                    *
                   / \
                  +   -
                 / \ / \
                3  4 5  2
 
Preorder traversal (prefix notation): * + 3 4 - 5 2
 
═══════════════════════════════════════════════════════════════════════════
 
Reading prefix notation:
• First symbol (*) is the operator
• Next group (+ 3 4) is left operand → evaluates to 7
• Next group (- 5 2) is right operand → evaluates to 3
• Final: 7 * 3 = 21
 
Why prefix is useful:
• No parentheses needed (unambiguous without them)
• Easy to evaluate with a stack
• Used in LISP, Scheme, and other functional languages
• Calculators like HP used a variant (Reverse Polish / postfix)

prefix-from-tree.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
 * Expression tree node
 */
interface ExprNode {
    value: string;  // Operator (+, -, *, /) or operand (number)
    left: ExprNode | null;
    right: ExprNode | null;
}
 
/**
 * Generate prefix notation from expression tree
 * Uses preorder traversal: operator BEFORE operands
 */
function toPrefix(root: ExprNode | null): string {
    if (root === null) {
        return "";
    }
    
    // Leaf node (operand)
    if (root.left === null && root.right === null) {
        return root.value;
    }
    
    // Internal node (operator) - preorder: visit, left, right
    const operator = root.value;
    const leftExpr = toPrefix(root.left);
    const rightExpr = toPrefix(root.right);
    
    return `${operator} ${leftExpr} ${rightExpr}`;
}
 
// Example: (3 + 4) * (5 - 2)
const expressionTree: ExprNode = {
    value: "*",
    left: {
        value: "+",
        left: { value: "3", left: null, right: null },
        right: { value: "4", left: null, right: null },
    },
    right: {
        value: "-",
        left: { value: "5", left: null, right: null },
        right: { value: "2", left: null, right: null },
    },
};
 
console.log(toPrefix(expressionTree));
// Output: "* + 3 4 - 5 2"

Common Preorder Patterns

Preorder traversal appears in many problem patterns. Recognizing these patterns helps you quickly identify when preorder is the right approach:

preorder-path-pattern.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * Pattern: Tracking path from root to current node
 * 
 * Many tree problems need to know the path from root to current node.
 * Preorder is natural because we can BUILD the path as we descend.
 */
function printRootToLeafPaths<T>(
    root: TreeNode<T> | null,
    path: T[] = []
): void {
    if (root === null) {
        return;
    }
    
    // VISIT: Add current node to path (preorder - before children)
    path.push(root.value);
    
    // If leaf node, print the complete path
    if (root.left === null && root.right === null) {
        console.log("Path:", path.join(" → "));
    }
    
    // Recurse on children
    printRootToLeafPaths(root.left, path);
    printRootToLeafPaths(root.right, path);
    
    // Backtrack: remove current node when returning
    path.pop();
}
 
/*
 * Tree:        1
 *             / \
 *            2   3
 *           / \
 *          4   5
 *
 * Output:
 * Path: 1 → 2 → 4
 * Path: 1 → 2 → 5
 * Path: 1 → 3
 */

preorder-depth-pattern.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * Pattern: Track depth/level during traversal
 * 
 * Preorder lets us pass down information (like depth) to children.
 * This "top-down" information flow matches preorder naturally.
 */
function printNodesWithDepth<T>(
    root: TreeNode<T> | null,
    depth: number = 0
): void {
    if (root === null) {
        return;
    }
    
    // VISIT: Print node with its depth
    const indent = "  ".repeat(depth);
    console.log(`${indent}Level ${depth}: ${root.value}`);
    
    // Pass depth + 1 to children
    printNodesWithDepth(root.left, depth + 1);
    printNodesWithDepth(root.right, depth + 1);
}
 
/*
 * Tree:        A
 *             / \
 *            B   C
 *           /
 *          D
 *
 * Output:
 * Level 0: A
 *   Level 1: B
 *     Level 2: D
 *   Level 1: C
 */

Top-Down vs Bottom-Up

Summary: Mastering Preorder Traversal

You've now gained comprehensive understanding of preorder traversal. Let's consolidate the key points:

Key Takeaways

•Preorder = Root → Left → Right — Visit current node BEFORE processing children.
•"PRE" means process first — The root comes at the front, like a prefix.
•Recursive implementation is elegant — Three lines after base case: visit, left, right.
•Iterative uses stack with reversed push — Push right before left so left pops first.
•Time O(n), Space O(h) — Same complexity for both recursive and iterative.
•First element is always root — Critical property for reconstruction algorithms.
•Use for top-down problems — When parent info must be processed before children.
•Classic applications — Tree cloning, serialization, prefix expressions, directory listing.

When to choose preorder:

You need to process/create a node before its descendants
You're passing information DOWN the tree (top-down)
You need the root of each subtree identified first
The problem involves creating or copying tree structure

What's next:

Preorder Mastery Complete

2 / 5