[AlgoMastery]
Topics›Tree›Insert and Delete
📖

Insert and Delete

Tree
~20 min read
5 practice problems

Insert and Delete Operations in Trees

Overview

Insert and delete operations are fundamental tree operations that modify the tree structure while maintaining the tree's properties. These operations ensure that after modifications, the tree continues to satisfy its specific constraints (e.g., BST property, balance factor).

Insert Operations

1. Insert in Binary Search Tree (BST)

Recursive Approach

class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function insertInBST(root, value) {
    // Base case: if tree is empty, create new node
    if (root === null) {
        return new TreeNode(value);
    }
    
    // Recursive case: insert in appropriate subtree
    if (value < root.val) {
        root.left = insertInBST(root.left, value);
    } else if (value > root.val) {
        root.right = insertInBST(root.right, value);
    }
    // If value equals root.val, we don't insert (no duplicates)
    
    return root;
}

Iterative Approach

function insertInBSTIterative(root, value) {
    if (root === null) return new TreeNode(value);
    
    let current = root;
    
    while (true) {
        if (value < current.val) {
            if (current.left === null) {
                current.left = new TreeNode(value);
                break;
            }
            current = current.left;
        } else if (value > current.val) {
            if (current.right === null) {
                current.right = new TreeNode(value);
                break;
            }
            current = current.right;
        } else {
            // Value already exists, don't insert
            break;
        }
    }
    
    return root;
}

2. Insert in Complete Binary Tree

Level-order Insertion

function insertInCompleteTree(root, value) {
    if (root === null) return new TreeNode(value);
    
    const queue = [root];
    
    while (queue.length > 0) {
        const node = queue.shift();
        
        // Insert left child if available
        if (node.left === null) {
            node.left = new TreeNode(value);
            return root;
        }
        
        // Insert right child if available
        if (node.right === null) {
            node.right = new TreeNode(value);
            return root;
        }
        
        // Add children to queue for processing
        if (node.left) queue.push(node.left);
        if (node.right) queue.push(node.right);
    }
    
    return root;
}

3. Insert in AVL Tree (Self-Balancing)

Basic AVL Insert

class AVLNode {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
        this.height = 1;
    }
}

function getBalanceFactor(node) {
    if (node === null) return 0;
    return getHeight(node.left) - getHeight(node.right);
}

function getHeight(node) {
    if (node === null) return 0;
    return node.height;
}

function updateHeight(node) {
    if (node !== null) {
        node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));
    }
}

function rotateRight(y) {
    const x = y.left;
    const T2 = x.right;
    
    // Perform rotation
    x.right = y;
    y.left = T2;
    
    // Update heights
    updateHeight(y);
    updateHeight(x);
    
    return x;
}

function rotateLeft(x) {
    const y = x.right;
    const T2 = y.left;
    
    // Perform rotation
    y.left = x;
    x.right = T2;
    
    // Update heights
    updateHeight(x);
    updateHeight(y);
    
    return y;
}

function insertInAVL(root, value) {
    // Step 1: Perform normal BST insertion
    if (root === null) return new AVLNode(value);
    
    if (value < root.val) {
        root.left = insertInAVL(root.left, value);
    } else if (value > root.val) {
        root.right = insertInAVL(root.right, value);
    } else {
        // Duplicate values not allowed in AVL trees
        return root;
    }
    
    // Step 2: Update height of current node
    updateHeight(root);
    
    // Step 3: Get balance factor
    const balanceFactor = getBalanceFactor(root);
    
    // Step 4: Perform rotations if unbalanced
    
    // Left-Left case
    if (balanceFactor > 1 && value < root.left.val) {
        return rotateRight(root);
    }
    
    // Right-Right case
    if (balanceFactor < -1 && value > root.right.val) {
        return rotateLeft(root);
    }
    
    // Left-Right case
    if (balanceFactor > 1 && value > root.left.val) {
        root.left = rotateLeft(root.left);
        return rotateRight(root);
    }
    
    // Right-Left case
    if (balanceFactor < -1 && value < root.right.val) {
        root.right = rotateRight(root.right);
        return rotateLeft(root);
    }
    
    return root;
}

Delete Operations

1. Delete from BST

Basic BST Deletion

function deleteFromBST(root, value) {
    // Base case: tree is empty
    if (root === null) return null;
    
    // Find the node to delete
    if (value < root.val) {
        root.left = deleteFromBST(root.left, value);
    } else if (value > root.val) {
        root.right = deleteFromBST(root.right, value);
    } else {
        // Node to be deleted found
        
        // Case 1: Node has no children (leaf node)
        if (root.left === null && root.right === null) {
            return null;
        }
        
        // Case 2: Node has one child
        if (root.left === null) {
            return root.right;
        }
        if (root.right === null) {
            return root.left;
        }
        
        // Case 3: Node has two children
        // Find inorder successor (smallest in right subtree)
        const successor = findMin(root.right);
        
        // Replace node's value with successor's value
        root.val = successor.val;
        
        // Delete the successor
        root.right = deleteFromBST(root.right, successor.val);
    }
    
    return root;
}

function findMin(node) {
    while (node.left !== null) {
        node = node.left;
    }
    return node;
}

2. Delete from Complete Binary Tree

Level-order Deletion

function deleteFromCompleteTree(root, value) {
    if (root === null) return null;
    
    // Find the node to delete and its parent
    const queue = [root];
    let parent = null;
    let targetNode = null;
    
    // Find the node to delete and its parent
    while (queue.length > 0) {
        const node = queue.shift();
        
        if (node.val === value) {
            targetNode = node;
            break;
        }
        
        if (node.left) {
            queue.push(node.left);
        }
        if (node.right) {
            queue.push(node.right);
        }
    }
    
    if (targetNode === null) return root; // Value not found
    
    // Find the last node in complete tree
    const lastNode = findLastNode(root);
    
    // Replace target value with last node's value
    targetNode.val = lastNode.val;
    
    // Remove the last node (this is more complex in complete trees)
    return root;
}

function findLastNode(root) {
    if (root === null) return null;
    
    const queue = [root];
    let lastNode = root;
    
    while (queue.length > 0) {
        const node = queue.shift();
        lastNode = node;
        
        if (node.left) queue.push(node.left);
        if (node.right) queue.push(node.right);
    }
    
    return lastNode;
}

3. Delete from AVL Tree

Complete AVL Deletion

function deleteFromAVL(root, value) {
    // Step 1: Perform normal BST deletion
    if (root === null) return root;
    
    if (value < root.val) {
        root.left = deleteFromAVL(root.left, value);
    } else if (value > root.val) {
        root.right = deleteFromAVL(root.right, value);
    } else {
        // Node to be deleted found
        
        // Case 1: Node has no children (leaf)
        if (root.left === null && root.right === null) {
            return null;
        }
        
        // Case 2: Node has one child
        if (root.left === null) {
            return root.right;
        }
        if (root.right === null) {
            return root.left;
        }
        
        // Case 3: Node has two children
        const successor = findMin(root.right);
        root.val = successor.val;
        root.right = deleteFromAVL(root.right, successor.val);
    }
    
    // Step 2: Update height of current node
    updateHeight(root);
    
    // Step 3: Get balance factor
    const balanceFactor = getBalanceFactor(root);
    
    // Step 4: Perform rotations if unbalanced
    
    // Left-Left case
    if (balanceFactor > 1 && getBalanceFactor(root.left) >= 0) {
        return rotateRight(root);
    }
    
    // Left-Right case
    if (balanceFactor > 1 && getBalanceFactor(root.left) < 0) {
        root.left = rotateLeft(root.left);
        return rotateRight(root);
    }
    
    // Right-Right case
    if (balanceFactor < -1 && getBalanceFactor(root.right) <= 0) {
        return rotateLeft(root);
    }
    
    // Right-Left case
    if (balanceFactor < -1 && getBalanceFactor(root.right) > 0) {
        root.right = rotateRight(root.right);
        return rotateLeft(root);
    }
    
    return root;
}

Tree Balance Maintenance

1. AVL Tree Rebalancing

Complete AVL Insert/Remove Operations

class AVLTree {
    constructor() {
        this.root = null;
    }
    
    insert(value) {
        this.root = this._insert(this.root, value);
    }
    
    _insert(node, value) {
        // Standard BST insertion
        if (node === null) return new AVLNode(value);
        
        if (value < node.val) {
            node.left = this._insert(node.left, value);
        } else if (value > node.val) {
            node.right = this._insert(node.right, value);
        } else {
            return node; // Duplicate values not allowed
        }
        
        // Update height
        updateHeight(node);
        
        // Get balance factor
        const balanceFactor = getBalanceFactor(node);
        
        // Left-Left case
        if (balanceFactor > 1 && value < node.left.val) {
            return rotateRight(node);
        }
        
        // Right-Right case
        if (balanceFactor < -1 && value > node.right.val) {
            return rotateLeft(node);
        }
        
        // Left-Right case
        if (balanceFactor > 1 && value > node.left.val) {
            node.left = rotateLeft(node.left);
            return rotateRight(node);
        }
        
        // Right-Left case
        if (balanceFactor < -1 && value < node.right.val) {
            node.right = rotateRight(node.right);
            return rotateLeft(node);
        }
        
        return node;
    }
    
    delete(value) {
        this.root = this._delete(this.root, value);
    }
    
    _delete(node, value) {
        // Standard BST deletion
        if (node === null) return node;
        
        if (value < node.val) {
            node.left = this._delete(node.left, value);
        } else if (value > node.val) {
            node.right = this._delete(node.right, value);
        } else {
            // Node to delete found
            if (node.left === null) return node.right;
            if (node.right === null) return node.left;
            
            // Node with two children
            const successor = findMin(node.right);
            node.val = successor.val;
            node.right = this._delete(node.right, successor.val);
        }
        
        // Update height and balance
        updateHeight(node);
        const balanceFactor = getBalanceFactor(node);
        
        // Rebalance if needed
        if (balanceFactor > 1) {
            if (getBalanceFactor(node.left) >= 0) {
                return rotateRight(node);
            } else {
                node.left = rotateLeft(node.left);
                return rotateRight(node);
            }
        }
        
        if (balanceFactor < -1) {
            if (getBalanceFactor(node.right) <= 0) {
                return rotateLeft(node);
            } else {
                node.right = rotateRight(node.right);
                return rotateLeft(node);
            }
        }
        
        return node;
    }
}

2. Red-Black Tree Operations

Basic RB Tree Insertion

class RedBlackNode {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
        this.color = 'RED';
        this.parent = null;
    }
}

function insertInRedBlackTree(root, value) {
    const newNode = new RedBlackNode(value);
    
    // Standard BST insertion
    root = insertBST(root, newNode);
    
    // Fix Red-Black properties
    return fixRedBlackProperties(root, newNode);
}

function insertBST(root, newNode) {
    if (root === null) return newNode;
    
    if (newNode.val < root.val) {
        root.left = insertBST(root.left, newNode);
        root.left.parent = root;
    } else if (newNode.val > root.val) {
        root.right = insertBST(root.right, newNode);
        root.right.parent = root;
    }
    
    return root;
}

function fixRedBlackProperties(root, node) {
    // Implementation of Red-Black tree balancing rules
    // This is a simplified version - full implementation requires complex rotation logic
    return root;
}

Time and Space Complexity

| Operation | Time Complexity | Space Complexity |

|-----------|----------------|------------------|

| BST Insert | O(log n) avg, O(n) worst | O(h) |

| BST Delete | O(log n) avg, O(n) worst | O(h) |

| AVL Insert | O(log n) | O(h) |

| AVL Delete | O(log n) | O(h) |

| Complete Tree Insert | O(log n) | O(w) |

Where:

  • n = number of nodes in tree
  • h = height of tree (recursion stack space)
  • w = maximum width of tree (queue space)

Common Variations

1. BST with Duplicate Values

function insertBSTWithDuplicates(root, value) {
    if (root === null) return new TreeNode(value);
    
    // Allow duplicates in right subtree
    if (value <= root.val) {
        root.left = insertBSTWithDuplicates(root.left, value);
    } else {
        root.right = insertBSTWithDuplicates(root.right, value);
    }
    
    return root;
}

2. BST with Count Tracking

class TreeNodeWithCount {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
        this.count = 1; // Number of occurrences
    }
}

function insertBSTWithCount(root, value) {
    if (root === null) return new TreeNodeWithCount(value);
    
    if (value < root.val) {
        root.left = insertBSTWithCount(root.left, value);
    } else if (value > root.val) {
        root.right = insertBSTWithCount(root.right, value);
    } else {
        root.count++; // Increment count for duplicates
    }
    
    return root;
}

3. Threaded Binary Tree Insertion

function insertInThreadedTree(root, value) {
    // Implementation for threaded trees (with predecessor/successor links)
    // This is more complex and specific to threaded tree structure
    return root;
}

Common Mistakes to Avoid

1. Incorrect Node Replacement

// ❌ Wrong - Not properly handling node replacement in deletion
function wrongDelete(root, value) {
    if (root === null) return null;
    
    if (value < root.val) {
        root.left = delete(root.left, value);
    } else if (value > root.val) {
        root.right = delete(root.right, value);
    } else {
        // Wrong: Not handling all cases properly
        if (root.left === null) return root.right;
        if (root.right === null) return root.left;
        
        // Missing proper replacement logic
        return root; // Wrong - should replace with successor
    }
    
    return root;
}

2. Missing Height Updates

// ❌ Wrong - Not updating heights in balanced trees
function wrongAVLInsert(root, value) {
    // Missing height update logic
    if (root === null) return new AVLNode(value);
    
    // Insert normally but don't update heights
    if (value < root.val) {
        root.left = insert(root.left, value);
    } else if (value > root.val) {
        root.right = insert(root.right, value);
    }
    
    // Missing rotation logic and height updates
    return root;
}

3. Inefficient Search During Insertion

// ❌ Wrong - Not leveraging BST properties efficiently
function inefficientInsert(root, value) {
    // This approach doesn't use the BST property effectively
    const queue = [root];
    
    while (queue.length > 0) {
        const node = queue.shift();
        
        if (node === null) continue;
        
        // Inefficient - not leveraging ordering
        if (value < node.val) {
            queue.push(node.left);
        } else {
            queue.push(node.right);
        }
    }
    
    return root;
}

Real-World Applications

1. Database Indexing Systems

// BST-based indexing for fast lookups
class DatabaseIndex {
    constructor() {
        this.bst = null;
    }
    
    insert(key, value) {
        this.bst = insertInBST(this.bst, {key, value});
    }
    
    delete(key) {
        this.bst = deleteFromBST(this.bst, key);
    }
    
    search(key) {
        return searchInBST(this.bst, key);
    }
}

2. File System Directory Structures

// Tree-based file system with ordered directory structure
class FileSystemTree {
    constructor() {
        this.root = null;
    }
    
    insertDirectory(path) {
        // Insert directory in appropriate position maintaining order
        this.root = insertInCompleteTree(this.root, path);
    }
    
    deleteDirectory(path) {
        // Remove directory and maintain tree structure
        this.root = deleteFromCompleteTree(this.root, path);
    }
}

3. Memory Management

// Memory allocation using balanced trees for efficient free block management
class MemoryManager {
    constructor() {
        this.freeBlocks = new AVLTree(); // Balanced tree for efficient allocation
    }
    
    allocate(size) {
        // Find best fit using tree operations
        return this.findBestFit(size);
    }
    
    deallocate(block) {
        // Insert back into balanced tree structure
        this.freeBlocks.insert(block);
    }
}

Performance Optimization Tips

1. Iterative Approaches

function iterativeBSTInsert(root, value) {
    if (root === null) return new TreeNode(value);
    
    let current = root;
    
    while (true) {
        if (value < current.val) {
            if (current.left === null) {
                current.left = new TreeNode(value);
                break;
            }
            current = current.left;
        } else if (value > current.val) {
            if (current.right === null) {
                current.right = new TreeNode(value);
                break;
            }
            current = current.right;
        } else {
            // Handle duplicates
            break;
        }
    }
    
    return root;
}

2. Batch Operations

function batchInsertBST(root, values) {
    // Insert multiple values efficiently
    for (const value of values) {
        root = insertInBST(root, value);
    }
    
    return root;
}

function batchDeleteBST(root, values) {
    // Delete multiple values efficiently
    for (const value of values) {
        root = deleteFromBST(root, value);
    }
    
    return root;
}

3. Optimized AVL Tree Operations

function optimizedAVLInsert(root, value) {
    // Use iterative approach to avoid stack overflow
    const stack = [];
    
    // Find insertion point
    let current = root;
    while (current !== null) {
        stack.push(current);
        if (value < current.val) {
            current = current.left;
        } else if (value > current.val) {
            current = current.right;
        } else {
            return root; // Value already exists
        }
    }
    
    // Insert new node
    const newNode = new AVLNode(value);
    
    // Handle root case
    if (stack.length === 0) {
        return newNode;
    }
    
    // Find parent and attach new node
    const parent = stack[stack.length - 1];
    if (value < parent.val) {
        parent.left = newNode;
    } else {
        parent.right = newNode;
    }
    
    // Rebalance from bottom up
    return rebalanceFromStack(stack, newNode);
}

Common Interview Patterns

1. Basic BST Operations

function basicBSTOperations() {
    // Implement insert and delete for BST
    function insert(root, value) {
        if (root === null) return new TreeNode(value);
        
        if (value < root.val) {
            root.left = insert(root.left, value);
        } else if (value > root.val) {
            root.right = insert(root.right, value);
        }
        
        return root;
    }
    
    function deleteNode(root, value) {
        if (root === null) return null;
        
        if (value < root.val) {
            root.left = deleteNode(root.left, value);
        } else if (value > root.val) {
            root.right = deleteNode(root.right, value);
        } else {
            // Node to delete found
            if (root.left === null) return root.right;
            if (root.right === null) return root.left;
            
            const successor = findMin(root.right);
            root.val = successor.val;
            root.right = deleteNode(root.right, successor.val);
        }
        
        return root;
    }
    
    return { insert, deleteNode };
}

2. AVL Tree Operations

function avlTreeOperations() {
    // Implement complete AVL tree operations with rotations
    function insertAVL(root, value) {
        // Implementation of AVL insertion with rotations
        return root;
    }
    
    function deleteAVL(root, value) {
        // Implementation of AVL deletion with rotations
        return root;
    }
    
    return { insertAVL, deleteAVL };
}

3. Complete Tree Operations

function completeTreeOperations() {
    function insertComplete(root, value) {
        // Insert maintaining complete tree property
        return root;
    }
    
    function deleteComplete(root, value) {
        // Delete maintaining complete tree property
        return root;
    }
    
    return { insertComplete, deleteComplete };
}

Best Practices

1. Consistent Tree Properties

Always maintain the specific properties of each tree type (BST, AVL, etc.)

2. Proper Node Management

Handle all edge cases: empty trees, single nodes, duplicate values

3. Balance Maintenance

For self-balancing trees, ensure rotations and rebalancing occur correctly

4. Memory Management

Properly handle node allocation and deallocation to prevent memory leaks

Key Takeaways

  1. Insertion is Fundamental: Basic tree operations that maintain structural integrity
  2. Balance is Critical: Self-balancing trees require careful rotation handling
  3. Multiple Approaches: Different strategies for different tree types (recursive vs iterative)
  4. Real-World Impact: Essential for database systems, file systems, and memory management
  5. Performance Considerations: Balance between operation speed and space efficiency

Insert and delete operations form the core of dynamic tree manipulation, enabling efficient data structure evolution while maintaining essential properties for optimal performance in various applications.

← PreviousSearch in TreeNext →Insert and Delete