BST Insertion - Learning Module

Loading content...

0/276

Algorithmic Steps

From Concept to Algorithm

We've established the conceptual foundations: BST insertion must maintain order, every value has a unique position, and navigation follows a single root-to-leaf path. Now it's time to crystallize this understanding into precise, executable algorithms.

This page presents the complete BST insertion algorithm in multiple forms—from high-level pseudocode to production-ready implementations. We'll trace through executions step by step, examine both recursive and iterative approaches, and understand exactly how each line contributes to the operation's correctness and efficiency.

What You Will Learn

By the end of this page, you will be able to: (1) Write BST insertion from memory in both recursive and iterative forms, (2) Trace through any insertion on paper and predict the resulting tree, (3) Understand the purpose of every algorithmic step, (4) Identify and handle edge cases correctly, and (5) Choose between recursive and iterative implementations based on context.

High-Level Algorithm: The Insertion Recipe

Before diving into code, let's establish the algorithm in plain English. This provides a reference point that transcends any specific programming language.

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
ALGORITHM: BST-Insert
INPUT: Tree T (may be empty), Value V to insert
OUTPUT: Tree T with V inserted in correct position
 
═══════════════════════════════════════════════════════════════════
 
STEP 1: Handle empty tree
    IF T is empty (root is null):
        Create new node with value V
        Set this node as the root of T
        RETURN T
    
STEP 2: Initialize navigation
    Set current = root of T
    Set parent = null
 
STEP 3: Navigate to insertion point
    WHILE current is not null:
        Set parent = current
        IF V < current.value:
            Set current = current.left
        ELSE IF V > current.value:
            Set current = current.right
        ELSE:  (V = current.value, duplicate)
            Handle according to duplicate policy
            RETURN (or continue navigation)
 
STEP 4: Create and attach new node
    Create new node N with value V
    IF V < parent.value:
        Set parent.left = N
    ELSE:
        Set parent.right = N
 
STEP 5: Return
    RETURN T (root unchanged unless tree was empty)
 
═══════════════════════════════════════════════════════════════════
 
PROPERTIES:
- Time:  O(h) where h = tree height
- Space: O(1) additional (iterative) or O(h) stack (recursive)
- Invariant: BST property preserved

Step-by-Step Breakdown:

Step 1 (Empty Tree): This is our base case. If there's no tree yet, the inserted value becomes the root. This handles the special case where we're starting from nothing.

Step 2 (Initialize): We set up our navigation. current is where we are in the tree; parent remembers where we came from for attachment later.

Step 3 (Navigate): The core loop. We traverse down the tree, going left or right based on comparisons. Each iteration moves one level deeper. We stop when current becomes null—that's our insertion point.

Step 4 (Attach): Having found the insertion point (null) and remembered the parent, we create the new node and link it. The comparison with parent.value determines whether it's a left or right child.

Step 5 (Return): We return the tree root. For non-empty trees, the root is unchanged. For empty trees, the root is the new node.

Recursive Implementation: Elegance Through Self-Reference

The recursive implementation of BST insertion is widely considered the most elegant approach. It captures the inherently recursive structure of trees and handles parent-child linking automatically through return values.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * Binary Search Tree Node
 * Each node stores a value and optional references to left and right children.
 */
class TreeNode {
    value: number;
    left: TreeNode | null;
    right: TreeNode | null;
    
    constructor(value: number) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

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
/**
 * Recursively inserts a value into a BST.
 * 
 * @param node - Current subtree root (may be null)
 * @param value - Value to insert
 * @returns Root of the subtree after insertion
 * 
 * Time Complexity: O(h) where h is tree height
 * Space Complexity: O(h) due to recursion stack
 */
function insertRecursive(node: TreeNode | null, value: number): TreeNode {
    // BASE CASE: Reached null - this is the insertion point
    // Create and return a new node; the caller will link it
    if (node === null) {
        return new TreeNode(value);
    }
    
    // RECURSIVE CASES: Navigate based on comparison
    if (value < node.value) {
        // Value belongs in left subtree
        // Recursively insert, then update left pointer
        node.left = insertRecursive(node.left, value);
    } else if (value > node.value) {
        // Value belongs in right subtree
        // Recursively insert, then update right pointer
        node.right = insertRecursive(node.right, value);
    } else {
        // DUPLICATE: Value already exists
        // Policy: Do nothing (skip duplicates)
        // Alternative policies: update data, go left, go right
    }
    
    // Return subtree root (possibly unchanged, possibly ancestor of new node)
    return node;
}
 
// Usage
let root: TreeNode | null = null;
root = insertRecursive(root, 50);  // First insertion: 50 becomes root
root = insertRecursive(root, 30);  // Insert 30 as left child
root = insertRecursive(root, 70);  // Insert 70 as right child
root = insertRecursive(root, 40);  // Insert 40 as right child of 30

The Assignment Pattern

Notice the pattern: node.left = insertRecursive(node.left, value). Even if node.left was already non-null and unchanged, reassigning it to itself is harmless. This uniform pattern handles both 'create new subtree' and 'subtree unchanged' cases elegantly.

Why the Recursive Approach Works:

Structural recursion: Trees are recursive structures (each subtree is itself a tree). Recursive algorithms naturally mirror this structure.
Implicit parent tracking: The call stack remembers all ancestors. When we return, we're back at the parent, ready to update its pointer.
Clean base case: The null check provides a clear termination condition and the precise insertion point.
Uniform treatment: Every call follows the same pattern—check for null, compare, recurse, return. No special cases mid-algorithm.

Iterative Implementation: Explicit Control

The iterative approach trades the elegance of recursion for explicit control over the navigation process. This is often preferred in production code due to stack space considerations and because it makes the algorithm's flow more visible.

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
/**
 * Iteratively inserts a value into a BST.
 * 
 * @param root - Current root of the tree (may be null)
 * @param value - Value to insert
 * @returns Root of the tree after insertion
 * 
 * Time Complexity: O(h) where h is tree height
 * Space Complexity: O(1) - only fixed number of pointers used
 */
function insertIterative(root: TreeNode | null, value: number): TreeNode {
    // Create the new node upfront
    const newNode = new TreeNode(value);
    
    // SPECIAL CASE: Empty tree
    if (root === null) {
        return newNode;  // New node becomes root
    }
    
    // Initialize navigation pointers
    let current: TreeNode | null = root;
    let parent: TreeNode | null = null;
    
    // PHASE 1: Navigate to find insertion point
    while (current !== null) {
        // Always remember parent before moving
        parent = current;
        
        if (value < current.value) {
            // Go left
            current = current.left;
        } else if (value > current.value) {
            // Go right
            current = current.right;
        } else {
            // DUPLICATE: Value already exists
            // Policy: Return unchanged tree (skip duplicate)
            return root;
        }
    }
    
    // PHASE 2: Attach new node to parent
    // current is null; parent is the node that will be new node's parent
    if (value < parent!.value) {
        parent!.left = newNode;
    } else {
        parent!.right = newNode;
    }
    
    // Return original root (unchanged)
    return root;
}
 
// Usage (same interface as recursive)
let root: TreeNode | null = null;
root = insertIterative(root, 50);
root = insertIterative(root, 30);
root = insertIterative(root, 70);
root = insertIterative(root, 40);

Key Differences from Recursive:

Aspect	Recursive	Iterative
Stack usage	O(h) - implicit recursion stack	O(1) - only a few pointers
Parent tracking	Implicit (call stack)	Explicit (parent variable)
Attachment	Via return value assignment	Via explicit parent.left/right assignment
Readability	More elegant for tree operations	More explicit, easier to debug step-by-step
Stack overflow risk	Yes, for very deep trees	No
Tail call optimization	Not applicable (assignment after call)	N/A

Stack Overflow Consideration

For very deep trees (height in thousands), the recursive approach may cause stack overflow. The iterative approach is safer for potentially unbalanced trees. In languages with tail call optimization, a tail-recursive version could avoid this, but standard BST insertion is not naturally tail-recursive.

Step-by-Step Execution Trace

Let's trace through a complete insertion scenario, showing exactly how the algorithm executes. We'll insert values [50, 30, 70, 20, 40, 60, 80] one by one, building a balanced BST.

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
════════════════════════════════════════════════════════════════════════
INSERTION 1: Insert 50 into empty tree
════════════════════════════════════════════════════════════════════════
┌─────────────────────────────────────┐
│ root = null                         │
│ value = 50                          │
│                                     │
│ Step: root is null → create node    │
│ Action: return new TreeNode(50)     │
│                                     │
│ Result: root = 50                   │
└─────────────────────────────────────┘
 
Tree after:    50
 
════════════════════════════════════════════════════════════════════════
INSERTION 2: Insert 30 into tree
════════════════════════════════════════════════════════════════════════
┌─────────────────────────────────────┐
│ At node: 50                         │
│ Compare: 30 < 50                    │
│ Decision: Go LEFT                   │
│                                     │
│ At node: null (50.left)             │
│ Action: Create node(30)             │
│ Link: 50.left = node(30)            │
└─────────────────────────────────────┘
 
Tree after:    50
              /
            30
 
════════════════════════════════════════════════════════════════════════
INSERTION 3: Insert 70 into tree
════════════════════════════════════════════════════════════════════════
┌─────────────────────────────────────┐
│ At node: 50                         │
│ Compare: 70 > 50                    │
│ Decision: Go RIGHT                  │
│                                     │
│ At node: null (50.right)            │
│ Action: Create node(70)             │
│ Link: 50.right = node(70)           │
└─────────────────────────────────────┘
 
Tree after:    50
              /  \
            30    70
 
════════════════════════════════════════════════════════════════════════
INSERTION 4: Insert 20 into tree
════════════════════════════════════════════════════════════════════════
┌─────────────────────────────────────┐
│ At node: 50                         │
│ Compare: 20 < 50 → Go LEFT          │
│                                     │
│ At node: 30                         │
│ Compare: 20 < 30 → Go LEFT          │
│                                     │
│ At node: null (30.left)             │
│ Action: Create node(20)             │
│ Link: 30.left = node(20)            │
└─────────────────────────────────────┘
 
Tree after:    50
              /  \
            30    70
           /
         20
 
════════════════════════════════════════════════════════════════════════
INSERTION 5: Insert 40 into tree
════════════════════════════════════════════════════════════════════════
┌─────────────────────────────────────┐
│ At node: 50                         │
│ Compare: 40 < 50 → Go LEFT          │
│                                     │
│ At node: 30                         │
│ Compare: 40 > 30 → Go RIGHT         │
│                                     │
│ At node: null (30.right)            │
│ Action: Create node(40)             │
│ Link: 30.right = node(40)           │
└─────────────────────────────────────┘
 
Tree after:    50
              /  \
            30    70
           /  \
         20   40
 
════════════════════════════════════════════════════════════════════════
INSERTION 6: Insert 60 into tree
════════════════════════════════════════════════════════════════════════
┌─────────────────────────────────────┐
│ At node: 50                         │
│ Compare: 60 > 50 → Go RIGHT         │
│                                     │
│ At node: 70                         │
│ Compare: 60 < 70 → Go LEFT          │
│                                     │
│ At node: null (70.left)             │
│ Action: Create node(60)             │
│ Link: 70.left = node(60)            │
└─────────────────────────────────────┘
 
Tree after:    50
              /  \
            30    70
           /  \  /
         20   40 60
 
════════════════════════════════════════════════════════════════════════
INSERTION 7: Insert 80 into tree
════════════════════════════════════════════════════════════════════════
┌─────────────────────────────────────┐
│ At node: 50                         │
│ Compare: 80 > 50 → Go RIGHT         │
│                                     │
│ At node: 70                         │
│ Compare: 80 > 70 → Go RIGHT         │
│                                     │
│ At node: null (70.right)            │
│ Action: Create node(80)             │
│ Link: 70.right = node(80)           │
└─────────────────────────────────────┘
 
FINAL TREE:
              50
            /    \
          30      70
         /  \    /  \
       20   40  60   80
 
Height: 2 (perfectly balanced!)
This structure achieved because we inserted the median first,
then values that evenly distributed left and right.

Observation on Insertion Order

Notice how inserting 50 first (the middle value) led to a balanced tree. If we had inserted [20, 30, 40, 50, 60, 70, 80] in sorted order, we'd get a completely degenerate tree (linked list). The same values, different order, vastly different structure.

Recursion Call Stack Visualization

Understanding how the recursive approach uses the call stack is crucial for both correctness and performance analysis. Let's trace the call stack for inserting 40 into a tree containing [50, 30, 70].

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
Initial tree:      50
                  /    \
                30      70
 
═══════════════════════════════════════════════════════════════════════
CALL STACK EVOLUTION (inserting 40)
═══════════════════════════════════════════════════════════════════════
 
▶ CALL 1: insertRecursive(node=50, value=40)
┌────────────────────────────────────────────────────────────────────┐
│ Stack: [call1(50)]                                                 │
│                                                                    │
│ node !== null ✓                                                    │
│ 40 < 50 → go left                                                  │
│ Execute: node.left = insertRecursive(node.left, 40)                │
│                      └──> This makes the next call                 │
└────────────────────────────────────────────────────────────────────┘
 
▶ CALL 2: insertRecursive(node=30, value=40)
┌────────────────────────────────────────────────────────────────────┐
│ Stack: [call1(50), call2(30)]                                      │
│                                                                    │
│ node !== null ✓                                                    │
│ 40 > 30 → go right                                                 │
│ Execute: node.right = insertRecursive(node.right, 40)              │
│                       └──> This makes the next call                │
└────────────────────────────────────────────────────────────────────┘
 
▶ CALL 3: insertRecursive(node=null, value=40)
┌────────────────────────────────────────────────────────────────────┐
│ Stack: [call1(50), call2(30), call3(null)]                         │
│                                                                    │
│ node === null ✓  ← BASE CASE REACHED!                              │
│ Action: return new TreeNode(40)                                    │
│                                                                    │
│ Return value: node(40)                                             │
│ Stack after return: [call1(50), call2(30)]                         │
└────────────────────────────────────────────────────────────────────┘
 
◀ RETURN TO CALL 2:
┌────────────────────────────────────────────────────────────────────┐
│ Stack: [call1(50), call2(30)]                                      │
│                                                                    │
│ Resuming: node.right = <returned value>                            │
│ Executes: 30.right = node(40)                                      │
│                                                                    │
│ Now 30 has right child 40!                                         │
│                                                                    │
│ Continue to: return node;  (return 30)                             │
│ Stack after return: [call1(50)]                                    │
└────────────────────────────────────────────────────────────────────┘
 
◀ RETURN TO CALL 1:
┌────────────────────────────────────────────────────────────────────┐
│ Stack: [call1(50)]                                                 │
│                                                                    │
│ Resuming: node.left = <returned value>                             │
│ Executes: 50.left = node(30)                                       │
│                                                                    │
│ Note: 50.left was already 30, so no change!                        │
│                                                                    │
│ Continue to: return node;  (return 50)                             │
│ Stack after return: []                                             │
└────────────────────────────────────────────────────────────────────┘
 
FINAL: root = 50 (returned from original call)
 
Result tree:       50
                  /    \
                30      70
                  \
                  40  ← NEW NODE

Key Observations:

Stack depth = path length + 1: We pushed 3 frames (for nodes 50, 30, and null). The insertion point was 2 edges from the root.
New node created only at base case: The TreeNode constructor is called exactly once, in the deepest (null) call.
Linking happens on the way up: The actual assignment 30.right = node(40) happens when call 2 resumes, not when call 3 executes.
Harmless reassignments: 50.left = 30 reassigns an already-correct pointer. This is benign and keeps the algorithm uniform.
Root unchanged for non-empty tree: The final return is 50 (original root), so root = insertRecursive(root, 40) maintains root = 50.

Handling Duplicates: Algorithm Variations

The standard BST property defines what happens when a value is less than or greater than a node. But what about equal values? Different applications require different duplicate handling strategies. Let's examine the common approaches.

Duplicate Handling Strategies
Strategy	Behavior	Use Case	Trade-off
Skip/Ignore	Do nothing, return tree unchanged	Unique key storage (sets)	Simple, but caller doesn't know if insert occurred
Count in Node	Increment a count field in existing node	Frequency counting, multisets	Compact, but changes node structure
Allow Left	Treat duplicates as 'less than' (go left)	Stable multiset ordering	Tree may become deeper/unbalanced
Allow Right	Treat duplicates as 'greater than' (go right)	Stable multiset ordering	Tree may become deeper/unbalanced
Replace/Update	Update value or associated data	Key-value stores where keys may repeat	Semantically different from 'insert'
Throw Error	Raise exception on duplicate	Strict unique constraint	Forces caller to check first

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
// Strategy 1: Skip duplicates (default in our examples)
function insertSkipDuplicates(node: TreeNode | null, value: number): TreeNode {
    if (node === null) return new TreeNode(value);
    
    if (value < node.value) {
        node.left = insertSkipDuplicates(node.left, value);
    } else if (value > node.value) {
        node.right = insertSkipDuplicates(node.right, value);
    }
    // else: value === node.value → do nothing (skip)
    
    return node;
}
 
// Strategy 2: Count duplicates
interface CountNode {
    value: number;
    count: number;  // How many times this value was inserted
    left: CountNode | null;
    right: CountNode | null;
}
 
function insertWithCount(node: CountNode | null, value: number): CountNode {
    if (node === null) {
        return { value, count: 1, left: null, right: null };
    }
    
    if (value < node.value) {
        node.left = insertWithCount(node.left, value);
    } else if (value > node.value) {
        node.right = insertWithCount(node.right, value);
    } else {
        node.count++;  // Duplicate: increment count
    }
    
    return node;
}
 
// Strategy 3: Allow duplicates (go right for equals)
function insertAllowDuplicates(node: TreeNode | null, value: number): TreeNode {
    if (node === null) return new TreeNode(value);
    
    if (value < node.value) {
        node.left = insertAllowDuplicates(node.left, value);
    } else {
        // value >= node.value → go right (includes duplicates)
        node.right = insertAllowDuplicates(node.right, value);
    }
    
    return node;
}

Choosing a Strategy

For most applications, either 'skip duplicates' (set semantics) or 'count in node' (multiset semantics) is appropriate. 'Allow duplicates' can cause tree imbalance if many duplicates exist. Always document your choice—it affects the tree's behavior and space usage.

Return Value Semantics

The return value of the insert function deserves careful attention. Different implementations return different things, and understanding what's returned (and why) is essential for correct usage.

Common Return Value Choices

•Return subtree root (our approach): The function returns the root of the (sub)tree after insertion. Callers update their pointer: root = insert(root, value). This handles empty trees elegantly.
•Return new node: Some implementations return a reference to the newly created node. Useful if the caller needs to immediately access or modify the new node.
•Return boolean: Return true if insertion occurred, false if value was duplicate. Simple but loses the ability to handle empty tree through return value.
•Return void (mutate in place): The tree is modified in place and nothing is returned. Requires the tree to be non-empty or wrapped in a class.

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
/**
 * BST class encapsulates root, simplifying insert interface.
 * Users don't need to reassign root after every insertion.
 */
class BST {
    private root: TreeNode | null = null;
    
    /**
     * Insert a value into the tree.
     * No return value needed—the class manages the root internally.
     */
    insert(value: number): void {
        this.root = this.insertRecursive(this.root, value);
    }
    
    private insertRecursive(node: TreeNode | null, value: number): TreeNode {
        if (node === null) {
            return new TreeNode(value);
        }
        
        if (value < node.value) {
            node.left = this.insertRecursive(node.left, value);
        } else if (value > node.value) {
            node.right = this.insertRecursive(node.right, value);
        }
        
        return node;
    }
}
 
// Usage - much cleaner!
const tree = new BST();
tree.insert(50);  // No need to capture return value
tree.insert(30);
tree.insert(70);

Why Return Subtree Root?

The 'return subtree root' approach is favored because:

Handles empty tree case: When root is null, the first insert creates the root and returns it. root = insert(null, 50) makes 50 the new root.
Uniform recursion: Every recursive call follows the same pattern. No special handling for 'is this the root?'
Enables immutable versions: If you wanted an immutable tree (common in functional programming), the return value represents the new tree version.
Composable with other operations: Balanced trees (AVL, Red-Black) that may rotate nodes rely on returning the new subtree root after rotations.

Common Mistakes and Pitfalls

BST insertion seems simple, but several common mistakes can lead to incorrect implementations. Let's examine these pitfalls and how to avoid them.

Common Mistakes

•Forgetting to update the root: Writing insert(root, value) instead of root = insert(root, value). The insertion happens, but if root was null, the caller's root variable stays null.
•Off-by-one in comparison: Using <= instead of < without understanding the duplicate policy implications. This changes where duplicates go.
•Not returning the node: In recursive version, forgetting return node; at the end. The linking breaks—modifications aren't propagated up.
•Creating multiple nodes: Creating the new node at the start of the recursive function instead of only at the base case. This wastes memory and could cause bugs.
•Modifying value instead of structure: Accidentally modifying node.value (data corruption) instead of node.left/right pointers.

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
// MISTAKE 1: Not capturing return value
let root: TreeNode | null = null;
insertRecursive(root, 50);  // WRONG! Root is still null
root = insertRecursive(root, 50);  // CORRECT
 
// MISTAKE 2: Forgetting to return node
function insertBroken(node: TreeNode | null, value: number): TreeNode | null {
    if (node === null) return new TreeNode(value);
    
    if (value < node.value) {
        node.left = insertBroken(node.left, value);
    } else if (value > node.value) {
        node.right = insertBroken(node.right, value);
    }
    
    // MISSING: return node;  ← Links won't propagate!
}
 
// MISTAKE 3: Creating node too early
function insertWasteful(node: TreeNode | null, value: number): TreeNode {
    const newNode = new TreeNode(value);  // Created every call!
    
    if (node === null) return newNode;  // OK here...
    
    if (value < node.value) {
        node.left = insertWasteful(node.left, value);  // Creates another node!
    }
    // ... nodes created but never used (wasted)
    
    return node;
}

Testing Your Implementation

Always test with: (1) empty tree, (2) single-node tree, (3) inserting smaller than all, (4) inserting larger than all, (5) inserting between existing values, (6) inserting duplicates. These cases catch most common bugs.

Summary: The Complete Insertion Algorithm

We've now covered the BST insertion algorithm in complete detail. Let's consolidate the key points:

Key Takeaways

•The algorithm is simple: Navigate using comparisons until null; create and attach new node. The elegance lies in this simplicity.
•Recursive implementation is elegant: The call stack handles parent tracking; return values handle linking. New node creation only happens at the base case.
•Iterative implementation is explicit: Parent tracking is manual; attachment is a separate step. No stack overhead, safer for deep trees.
•Both have O(h) time complexity: The work is proportional to tree height, whether we use recursion or iteration.
•Duplicate handling is a design choice: Skip, count, allow, or reject—pick a consistent policy for your use case.
•Return value semantics matter: Returning the subtree root enables uniform handling of empty trees and composability with balanced tree operations.
•Watch for common pitfalls: Always capture return values, always return the node at the end of recursive calls, test edge cases thoroughly.

What's Next:

With the algorithm mastered, we now turn to rigorous complexity analysis. The next page examines why BST insertion is O(h), what this means in terms of best, average, and worst cases, and how this complexity compares to other data structures.

Page Complete

You now have complete mastery of the BST insertion algorithm in both recursive and iterative forms. You can trace executions, handle edge cases, and choose appropriate duplicate policies. Next, we'll analyze the time complexity in depth.