Bst Deletion Operation - Learning Module

Loading content...

0/279

Maintaining the BST Property After Deletion

From Theory to Implementation: Preserving the Invariant

You now understand the three cases of BST deletion and the role of inorder successors and predecessors. But understanding the theory and writing correct code are different challenges.

In this page, we'll build a complete, production-ready BST deletion implementation. More importantly, we'll develop the invariant-thinking mindset that ensures every step of your implementation preserves the BST property.

The goal isn't just code that works—it's code that is provably correct because it maintains the BST invariant at every operation.

The Subtle Danger

BST deletion bugs are often latent. A broken implementation might appear to work for small trees or specific sequences, then fail catastrophically when:

• The tree grows larger • Certain deletion patterns emerge • Edge cases (root deletion, specific child configurations) occur

The only protection is rigorous invariant preservation—ensuring every step maintains left < node < right for ALL nodes.

The Complete Deletion Algorithm

Before diving into code, let's establish the complete algorithmic flow. BST deletion consists of two phases:

Phase 1: Find the node to delete

Use standard BST search to locate the node
Track the parent as we descend (needed for pointer updates)
Handle the case where the value doesn't exist

Phase 2: Remove the node based on its case

Case 1 (Leaf): Disconnect from parent
Case 2 (One Child): Bypass with child
Case 3 (Two Children): Replace with successor/predecessor, then delete the replacement from its original location

Pseudocode Overview:

DELETE(tree, value):
    1. node, parent, isLeftChild = FIND_WITH_PARENT(tree.root, value)
    2. if node is null:
         return false  // value not found
    
    3. if node has two children:
         // Replace with inorder successor
         successor, succParent = FIND_SUCCESSOR_WITH_PARENT(node)
         node.value = successor.value
         // Now delete successor (which has at most 1 child)
         node = successor
         parent = succParent
         isLeftChild = (succParent.left == successor)
    
    4. // Now node has 0 or 1 child
       child = node.left OR node.right OR null
    
    5. if parent is null:
         tree.root = child  // Deleting root
       else if isLeftChild:
         parent.left = child
       else:
         parent.right = child
    
    6. return true

Notice how two-child deletion reduces to the simpler cases by first replacing the value, then handling the successor as a one-child or leaf case.

The Reduction Pattern

This algorithm demonstrates a powerful pattern: reducing complex cases to simpler ones.

We don't have THREE different deletion implementations—we have ONE algorithm where the complex case (two children) transforms into a simpler case (zero or one child) by cleverly repositioning what we're actually deleting.

Complete Production-Ready Implementation

Here's a complete, thoroughly-commented implementation of BST deletion. We'll use the inorder successor approach for two-child deletion.

bstDeletion.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
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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
interface TreeNode {
    value: number;
    left: TreeNode | null;
    right: TreeNode | null;
}
 
class BinarySearchTree {
    root: TreeNode | null = null;
 
    /**
     * Deletes a value from the BST.
     * Returns true if the value was found and deleted, false otherwise.
     * 
     * INVARIANT: After deletion, the BST property (left < node < right)
     * is preserved for ALL nodes in the tree.
     */
    delete(value: number): boolean {
        // Phase 1: Find the node and its parent
        const searchResult = this.findWithParent(value);
        
        if (searchResult === null) {
            return false; // Value not in tree
        }
        
        let { node, parent, isLeftChild } = searchResult;
        
        // Phase 2: Handle deletion based on case
        
        // CASE 3: Node has two children
        // Strategy: Replace with inorder successor, then delete successor
        if (node.left !== null && node.right !== null) {
            // Find inorder successor (leftmost in right subtree)
            const { successor, successorParent } = this.findSuccessorWithParent(node);
            
            // Copy successor's value to the node we're "deleting"
            // This preserves the BST property because:
            // - successor.value > all values in node's left subtree (proven earlier)
            // - successor.value < all values in node's right subtree except itself
            node.value = successor.value;
            
            // Now we need to delete the successor from its original position
            // The successor has at most one child (no left child by definition)
            node = successor;
            parent = successorParent;
            isLeftChild = (successorParent.left === successor);
        }
        
        // At this point, node has 0 or 1 child (CASE 1 or CASE 2)
        // We handle both uniformly: child is either the one child or null
        const child: TreeNode | null = 
            (node.left !== null) ? node.left : node.right;
        
        // Reconnect: parent should now point to child instead of node
        if (parent === null) {
            // We're deleting the root
            this.root = child;
        } else if (isLeftChild) {
            parent.left = child;
        } else {
            parent.right = child;
        }
        
        // Node is now disconnected; garbage collection will reclaim it
        return true;
    }
 
    /**
     * Finds a node and its parent.
     * Returns null if value not found.
     */
    private findWithParent(value: number): {
        node: TreeNode;
        parent: TreeNode | null;
        isLeftChild: boolean;
    } | null {
        let parent: TreeNode | null = null;
        let current: TreeNode | null = this.root;
        let isLeftChild = false;
        
        while (current !== null) {
            if (value === current.value) {
                return { node: current, parent, isLeftChild };
            }
            
            parent = current;
            if (value < current.value) {
                current = current.left;
                isLeftChild = true;
            } else {
                current = current.right;
                isLeftChild = false;
            }
        }
        
        return null; // Not found
    }
 
    /**
     * Finds the inorder successor of a node (assuming it has a right child)
     * and returns both the successor and its parent.
     */
    private findSuccessorWithParent(node: TreeNode): {
        successor: TreeNode;
        successorParent: TreeNode;
    } {
        // The successor is the leftmost node in the right subtree
        let successorParent: TreeNode = node;
        let successor: TreeNode = node.right!; // Guaranteed to exist in two-child case
        
        while (successor.left !== null) {
            successorParent = successor;
            successor = successor.left;
        }
        
        return { successor, successorParent };
    }
 
    /**
     * Standard BST insertion for building test trees.
     */
    insert(value: number): void {
        const newNode: TreeNode = { value, left: null, right: null };
        
        if (this.root === null) {
            this.root = newNode;
            return;
        }
        
        let current = this.root;
        while (true) {
            if (value < current.value) {
                if (current.left === null) {
                    current.left = newNode;
                    return;
                }
                current = current.left;
            } else {
                if (current.right === null) {
                    current.right = newNode;
                    return;
                }
                current = current.right;
            }
        }
    }
 
    /**
     * Inorder traversal - should always produce sorted output if BST property holds.
     */
    inorderTraversal(): number[] {
        const result: number[] = [];
        this.inorderHelper(this.root, result);
        return result;
    }
 
    private inorderHelper(node: TreeNode | null, result: number[]): void {
        if (node === null) return;
        this.inorderHelper(node.left, result);
        result.push(node.value);
        this.inorderHelper(node.right, result);
    }
}

Walking Through a Complete Example

Let's trace through a two-child deletion step by step to see how the algorithm preserves the BST property.

Initial Tree: Delete node 50 from this BST:

Converting Mermaid diagram...

Step 1: Identify the case

Node 50 has two children (30 and 70). This is Case 3.

Step 2: Find the inorder successor

Go right to 70, then left as far as possible:

70 → 60 → 55 → null

Successor = 55 (leftmost in right subtree)

Step 3: Copy successor's value

Replace 50 with 55. The node that held 50 now holds 55:

Converting Mermaid diagram...

Step 4: Delete the successor from its original position

Node 55 (original position) is a leaf node with no children.

This is Case 1! We simply disconnect it from its parent (60).

Final Tree:

Converting Mermaid diagram...

Verifying the BST Property

Let's verify the BST property at the modified positions:

At node 55 (formerly 50): • Left subtree: {20, 30, 35, 40, 45} — all < 55 ✓ • Right subtree: {60, 70, 85} — all > 55 ✓

At node 60: • Left subtree: empty (was 55, now deleted) ✓ • Right subtree: none ✓

Inorder traversal before: 20, 30, 35, 40, 45, 50, 55, 60, 70, 85 Inorder traversal after: 20, 30, 35, 40, 45, 55, 60, 70, 85

The tree remains a valid BST!

Edge Cases and Special Scenarios

Robust implementations must handle edge cases that break naive approaches. Here are the critical scenarios:

Edge Case: Deleting the Root

•Root is a leaf: Tree becomes empty (root = null)
•Root has one child: Child becomes new root
•Root has two children: Replace with successor, same algorithm applies
•The key: Check if parent is null and update tree.root instead of parent.left/right

Edge Case: Successor is Right Child

•Scenario: When finding successor, if the right child has no left subtree, the successor IS the right child
•Example: In the tree [10 → 5, 15], if we delete 10, the successor is 15 (right child directly)
•The subtlety: successorParent.left === successor only when we went left at least once
•Handle by: The isLeftChild check after determining successor handles this naturally

Example: Successor is immediate right child

Converting Mermaid diagram...

Here, 15 is both the right child AND the successor (no left subtree from 15).

After deletion:

Copy 15 to node 10's position
Delete 15 from its original position (it has one child: 20)
20 becomes the new right child of the node now holding 15

Converting Mermaid diagram...

Edge Case: Value Not Found

•Always check: The value might not be in the tree
•Return indicator: Return false/null to indicate no deletion occurred
•Don't assume existence: Never assume a value is present without checking

Invariant Verification: Proving Correctness

How do we know our implementation is correct? We use invariant verification—checking that the BST property holds after every operation.

The BST Invariant: For every node N:

All values in N's left subtree < N.value
All values in N's right subtree > N.value

Verification Approaches:

bstVerification.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
73
74
75
76
77
78
interface TreeNode {
    value: number;
    left: TreeNode | null;
    right: TreeNode | null;
}
 
/**
 * Verifies that the BST property holds for the entire tree.
 * Uses the range-based approach: track valid [min, max] for each node.
 */
function isValidBST(root: TreeNode | null): boolean {
    return isValidBSTHelper(root, -Infinity, Infinity);
}
 
function isValidBSTHelper(
    node: TreeNode | null,
    minValue: number,
    maxValue: number
): boolean {
    // Empty tree is valid
    if (node === null) return true;
    
    // Node must be within valid range
    if (node.value <= minValue || node.value >= maxValue) {
        return false;
    }
    
    // Left subtree: all values must be < node.value
    // Right subtree: all values must be > node.value
    return (
        isValidBSTHelper(node.left, minValue, node.value) &&
        isValidBSTHelper(node.right, node.value, maxValue)
    );
}
 
/**
 * Alternative verification: inorder traversal should be strictly increasing.
 */
function isValidBSTByInorder(root: TreeNode | null): boolean {
    const values: number[] = [];
    inorderCollect(root, values);
    
    for (let i = 1; i < values.length; i++) {
        if (values[i] <= values[i - 1]) {
            return false;
        }
    }
    return true;
}
 
function inorderCollect(node: TreeNode | null, result: number[]): void {
    if (node === null) return;
    inorderCollect(node.left, result);
    result.push(node.value);
    inorderCollect(node.right, result);
}
 
/**
 * Example usage in tests:
 */
function testDeletion(): void {
    const bst = new BinarySearchTree();
    [50, 30, 70, 20, 40, 60, 85, 35, 45, 55].forEach(v => bst.insert(v));
    
    console.log("Before deletion:", bst.inorderTraversal());
    console.log("Is valid BST:", isValidBST(bst.root));
    
    bst.delete(50);
    
    console.log("After deleting 50:", bst.inorderTraversal());
    console.log("Is valid BST:", isValidBST(bst.root));
    
    // Expected output:
    // Before deletion: [20, 30, 35, 40, 45, 50, 55, 60, 70, 85]
    // Is valid BST: true
    // After deleting 50: [20, 30, 35, 40, 45, 55, 60, 70, 85]
    // Is valid BST: true
}

Testing Strategy

For robust deletion testing:

Verify before and after each deletion
Test all cases: leaf, single-child, two-child
Test edge cases: root deletion, value not found, single-node tree
Stress test: Random insertions and deletions, verify after each
Check inorder: Should always be sorted (with deleted value missing)

Common Implementation Bugs and How to Avoid Them

BST deletion is notorious for subtle bugs. Here are the most common mistakes and how to avoid them:

Bug 1: Forgetting to Handle Root Deletion

•Symptom: Tree appears empty or corrupted after deleting root
•Cause: Updating parent.left/right when parent is null
•Fix: Check if parent is null and update tree.root instead

Bug 2: Incorrect isLeftChild After Finding Successor

•Symptom: Two-child deletion corrupts tree structure
•Cause: Using original isLeftChild when deleting successor
•Fix: Recalculate isLeftChild for successor: (successorParent.left === successor)

Bug 3: Lost Subtrees in Two-Child Deletion

•Symptom: Nodes disappear from tree after deletion
•Cause: Deleting the node instead of replacing its value
•Fix: Only copy the successor's VALUE, then delete successor from its position

Bug 4: Successor's Subtree Not Reconnected

•Symptom: Successor's right subtree is lost
•Cause: Treating successor as leaf when it has a right child
•Fix: Treat successor deletion as Case 1 or Case 2 (child might be non-null)

Debugging Tip

When deletion seems broken, print the inorder traversal before and after. If the output isn't sorted (excluding the deleted value), the BST property has been violated. Then trace backwards to find where the invariant broke.

Summary: Maintaining Correctness

Key Takeaways

•Two-child deletion reduces to simpler cases — replace value, then delete successor/predecessor
•Track parent pointers carefully — especially recalculate isLeftChild after finding successor
•Handle root as special case — update tree.root when parent is null
•Successor may have right child — don't assume it's always a leaf
•Verify with inorder traversal — sorted output proves BST property
•Test edge cases explicitly — root deletion, immediate successor, empty tree

Coming Next

In the next and final page, we'll analyze the time complexity of BST deletion in depth. You'll understand why deletion is O(h), how tree shape affects performance, and when BST deletion becomes problematic—setting the stage for self-balancing trees.

Maintaining the BST Property After Deletion

From Theory to Implementation: Preserving the Invariant

You now understand the three cases of BST deletion and the role of inorder successors and predecessors. But understanding the theory and writing correct code are different challenges.

The goal isn't just code that works—it's code that is provably correct because it maintains the BST invariant at every operation.

The Subtle Danger

BST deletion bugs are often latent. A broken implementation might appear to work for small trees or specific sequences, then fail catastrophically when:

• The tree grows larger • Certain deletion patterns emerge • Edge cases (root deletion, specific child configurations) occur

The only protection is rigorous invariant preservation—ensuring every step maintains left < node < right for ALL nodes.

The Complete Deletion Algorithm

Before diving into code, let's establish the complete algorithmic flow. BST deletion consists of two phases:

Phase 1: Find the node to delete

Use standard BST search to locate the node
Track the parent as we descend (needed for pointer updates)
Handle the case where the value doesn't exist

Phase 2: Remove the node based on its case

Case 1 (Leaf): Disconnect from parent
Case 2 (One Child): Bypass with child
Case 3 (Two Children): Replace with successor/predecessor, then delete the replacement from its original location

Pseudocode Overview:

DELETE(tree, value):
    1. node, parent, isLeftChild = FIND_WITH_PARENT(tree.root, value)
    2. if node is null:
         return false  // value not found
    
    3. if node has two children:
         // Replace with inorder successor
         successor, succParent = FIND_SUCCESSOR_WITH_PARENT(node)
         node.value = successor.value
         // Now delete successor (which has at most 1 child)
         node = successor
         parent = succParent
         isLeftChild = (succParent.left == successor)
    
    4. // Now node has 0 or 1 child
       child = node.left OR node.right OR null
    
    5. if parent is null:
         tree.root = child  // Deleting root
       else if isLeftChild:
         parent.left = child
       else:
         parent.right = child
    
    6. return true

Notice how two-child deletion reduces to the simpler cases by first replacing the value, then handling the successor as a one-child or leaf case.

The Reduction Pattern

This algorithm demonstrates a powerful pattern: reducing complex cases to simpler ones.

Complete Production-Ready Implementation

Here's a complete, thoroughly-commented implementation of BST deletion. We'll use the inorder successor approach for two-child deletion.

bstDeletion.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
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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
interface TreeNode {
    value: number;
    left: TreeNode | null;
    right: TreeNode | null;
}
 
class BinarySearchTree {
    root: TreeNode | null = null;
 
    /**
     * Deletes a value from the BST.
     * Returns true if the value was found and deleted, false otherwise.
     * 
     * INVARIANT: After deletion, the BST property (left < node < right)
     * is preserved for ALL nodes in the tree.
     */
    delete(value: number): boolean {
        // Phase 1: Find the node and its parent
        const searchResult = this.findWithParent(value);
        
        if (searchResult === null) {
            return false; // Value not in tree
        }
        
        let { node, parent, isLeftChild } = searchResult;
        
        // Phase 2: Handle deletion based on case
        
        // CASE 3: Node has two children
        // Strategy: Replace with inorder successor, then delete successor
        if (node.left !== null && node.right !== null) {
            // Find inorder successor (leftmost in right subtree)
            const { successor, successorParent } = this.findSuccessorWithParent(node);
            
            // Copy successor's value to the node we're "deleting"
            // This preserves the BST property because:
            // - successor.value > all values in node's left subtree (proven earlier)
            // - successor.value < all values in node's right subtree except itself
            node.value = successor.value;
            
            // Now we need to delete the successor from its original position
            // The successor has at most one child (no left child by definition)
            node = successor;
            parent = successorParent;
            isLeftChild = (successorParent.left === successor);
        }
        
        // At this point, node has 0 or 1 child (CASE 1 or CASE 2)
        // We handle both uniformly: child is either the one child or null
        const child: TreeNode | null = 
            (node.left !== null) ? node.left : node.right;
        
        // Reconnect: parent should now point to child instead of node
        if (parent === null) {
            // We're deleting the root
            this.root = child;
        } else if (isLeftChild) {
            parent.left = child;
        } else {
            parent.right = child;
        }
        
        // Node is now disconnected; garbage collection will reclaim it
        return true;
    }
 
    /**
     * Finds a node and its parent.
     * Returns null if value not found.
     */
    private findWithParent(value: number): {
        node: TreeNode;
        parent: TreeNode | null;
        isLeftChild: boolean;
    } | null {
        let parent: TreeNode | null = null;
        let current: TreeNode | null = this.root;
        let isLeftChild = false;
        
        while (current !== null) {
            if (value === current.value) {
                return { node: current, parent, isLeftChild };
            }
            
            parent = current;
            if (value < current.value) {
                current = current.left;
                isLeftChild = true;
            } else {
                current = current.right;
                isLeftChild = false;
            }
        }
        
        return null; // Not found
    }
 
    /**
     * Finds the inorder successor of a node (assuming it has a right child)
     * and returns both the successor and its parent.
     */
    private findSuccessorWithParent(node: TreeNode): {
        successor: TreeNode;
        successorParent: TreeNode;
    } {
        // The successor is the leftmost node in the right subtree
        let successorParent: TreeNode = node;
        let successor: TreeNode = node.right!; // Guaranteed to exist in two-child case
        
        while (successor.left !== null) {
            successorParent = successor;
            successor = successor.left;
        }
        
        return { successor, successorParent };
    }
 
    /**
     * Standard BST insertion for building test trees.
     */
    insert(value: number): void {
        const newNode: TreeNode = { value, left: null, right: null };
        
        if (this.root === null) {
            this.root = newNode;
            return;
        }
        
        let current = this.root;
        while (true) {
            if (value < current.value) {
                if (current.left === null) {
                    current.left = newNode;
                    return;
                }
                current = current.left;
            } else {
                if (current.right === null) {
                    current.right = newNode;
                    return;
                }
                current = current.right;
            }
        }
    }
 
    /**
     * Inorder traversal - should always produce sorted output if BST property holds.
     */
    inorderTraversal(): number[] {
        const result: number[] = [];
        this.inorderHelper(this.root, result);
        return result;
    }
 
    private inorderHelper(node: TreeNode | null, result: number[]): void {
        if (node === null) return;
        this.inorderHelper(node.left, result);
        result.push(node.value);
        this.inorderHelper(node.right, result);
    }
}

Walking Through a Complete Example

Let's trace through a two-child deletion step by step to see how the algorithm preserves the BST property.

Initial Tree: Delete node 50 from this BST:

Converting Mermaid diagram...

Step 1: Identify the case

Node 50 has two children (30 and 70). This is Case 3.

Step 2: Find the inorder successor

Go right to 70, then left as far as possible:

70 → 60 → 55 → null

Successor = 55 (leftmost in right subtree)

Step 3: Copy successor's value

Replace 50 with 55. The node that held 50 now holds 55:

Converting Mermaid diagram...

Step 4: Delete the successor from its original position

Node 55 (original position) is a leaf node with no children.

This is Case 1! We simply disconnect it from its parent (60).

Final Tree:

Converting Mermaid diagram...

Verifying the BST Property

Let's verify the BST property at the modified positions:

At node 55 (formerly 50): • Left subtree: {20, 30, 35, 40, 45} — all < 55 ✓ • Right subtree: {60, 70, 85} — all > 55 ✓

At node 60: • Left subtree: empty (was 55, now deleted) ✓ • Right subtree: none ✓

Inorder traversal before: 20, 30, 35, 40, 45, 50, 55, 60, 70, 85 Inorder traversal after: 20, 30, 35, 40, 45, 55, 60, 70, 85

The tree remains a valid BST!

Edge Cases and Special Scenarios

Robust implementations must handle edge cases that break naive approaches. Here are the critical scenarios:

Edge Case: Deleting the Root

•Root is a leaf: Tree becomes empty (root = null)
•Root has one child: Child becomes new root
•Root has two children: Replace with successor, same algorithm applies
•The key: Check if parent is null and update tree.root instead of parent.left/right

Edge Case: Successor is Right Child

•Scenario: When finding successor, if the right child has no left subtree, the successor IS the right child
•Example: In the tree [10 → 5, 15], if we delete 10, the successor is 15 (right child directly)
•The subtlety: successorParent.left === successor only when we went left at least once
•Handle by: The isLeftChild check after determining successor handles this naturally

Example: Successor is immediate right child

Converting Mermaid diagram...

Here, 15 is both the right child AND the successor (no left subtree from 15).

After deletion:

Copy 15 to node 10's position
Delete 15 from its original position (it has one child: 20)
20 becomes the new right child of the node now holding 15

Converting Mermaid diagram...

Edge Case: Value Not Found

•Always check: The value might not be in the tree
•Return indicator: Return false/null to indicate no deletion occurred
•Don't assume existence: Never assume a value is present without checking

Invariant Verification: Proving Correctness

How do we know our implementation is correct? We use invariant verification—checking that the BST property holds after every operation.

The BST Invariant: For every node N:

All values in N's left subtree < N.value
All values in N's right subtree > N.value

Verification Approaches:

bstVerification.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
73
74
75
76
77
78
interface TreeNode {
    value: number;
    left: TreeNode | null;
    right: TreeNode | null;
}
 
/**
 * Verifies that the BST property holds for the entire tree.
 * Uses the range-based approach: track valid [min, max] for each node.
 */
function isValidBST(root: TreeNode | null): boolean {
    return isValidBSTHelper(root, -Infinity, Infinity);
}
 
function isValidBSTHelper(
    node: TreeNode | null,
    minValue: number,
    maxValue: number
): boolean {
    // Empty tree is valid
    if (node === null) return true;
    
    // Node must be within valid range
    if (node.value <= minValue || node.value >= maxValue) {
        return false;
    }
    
    // Left subtree: all values must be < node.value
    // Right subtree: all values must be > node.value
    return (
        isValidBSTHelper(node.left, minValue, node.value) &&
        isValidBSTHelper(node.right, node.value, maxValue)
    );
}
 
/**
 * Alternative verification: inorder traversal should be strictly increasing.
 */
function isValidBSTByInorder(root: TreeNode | null): boolean {
    const values: number[] = [];
    inorderCollect(root, values);
    
    for (let i = 1; i < values.length; i++) {
        if (values[i] <= values[i - 1]) {
            return false;
        }
    }
    return true;
}
 
function inorderCollect(node: TreeNode | null, result: number[]): void {
    if (node === null) return;
    inorderCollect(node.left, result);
    result.push(node.value);
    inorderCollect(node.right, result);
}
 
/**
 * Example usage in tests:
 */
function testDeletion(): void {
    const bst = new BinarySearchTree();
    [50, 30, 70, 20, 40, 60, 85, 35, 45, 55].forEach(v => bst.insert(v));
    
    console.log("Before deletion:", bst.inorderTraversal());
    console.log("Is valid BST:", isValidBST(bst.root));
    
    bst.delete(50);
    
    console.log("After deleting 50:", bst.inorderTraversal());
    console.log("Is valid BST:", isValidBST(bst.root));
    
    // Expected output:
    // Before deletion: [20, 30, 35, 40, 45, 50, 55, 60, 70, 85]
    // Is valid BST: true
    // After deleting 50: [20, 30, 35, 40, 45, 55, 60, 70, 85]
    // Is valid BST: true
}

Testing Strategy

For robust deletion testing:

Verify before and after each deletion
Test all cases: leaf, single-child, two-child
Test edge cases: root deletion, value not found, single-node tree
Stress test: Random insertions and deletions, verify after each
Check inorder: Should always be sorted (with deleted value missing)

Common Implementation Bugs and How to Avoid Them

BST deletion is notorious for subtle bugs. Here are the most common mistakes and how to avoid them:

Bug 1: Forgetting to Handle Root Deletion

•Symptom: Tree appears empty or corrupted after deleting root
•Cause: Updating parent.left/right when parent is null
•Fix: Check if parent is null and update tree.root instead

Bug 2: Incorrect isLeftChild After Finding Successor

•Symptom: Two-child deletion corrupts tree structure
•Cause: Using original isLeftChild when deleting successor
•Fix: Recalculate isLeftChild for successor: (successorParent.left === successor)

Bug 3: Lost Subtrees in Two-Child Deletion

•Symptom: Nodes disappear from tree after deletion
•Cause: Deleting the node instead of replacing its value
•Fix: Only copy the successor's VALUE, then delete successor from its position

Bug 4: Successor's Subtree Not Reconnected

•Symptom: Successor's right subtree is lost
•Cause: Treating successor as leaf when it has a right child
•Fix: Treat successor deletion as Case 1 or Case 2 (child might be non-null)

Debugging Tip

Summary: Maintaining Correctness

Key Takeaways

•Two-child deletion reduces to simpler cases — replace value, then delete successor/predecessor
•Track parent pointers carefully — especially recalculate isLeftChild after finding successor
•Handle root as special case — update tree.root when parent is null
•Successor may have right child — don't assume it's always a leaf
•Verify with inorder traversal — sorted output proves BST property
•Test edge cases explicitly — root deletion, immediate successor, empty tree

Coming Next