Speed:

BST Advanced Operations

Min/Max: O(h)Predecessor: O(h)Successor: O(h)

🚀Advanced BST Operations

Locate the smallest element by traversing left until reaching the leftmost node.

Locate the largest element by traversing right until reaching the rightmost node.

Find the largest element smaller than the given value. Two cases based on left subtree.

Find the smallest element larger than the given value. Two cases based on right subtree.

⬇️Find Minimum

Finding the minimum element in a BST is straightforward due to its ordering property. Since all smaller values are stored in the left subtree, the minimum element is always the leftmost node in the tree. We simply traverse left from the root until we reach a node with no left child. This operation runs in O(h) time, where h is the height of the tree.

findMin(node = this.root) {
    if (node === null) return null;
    
    // Keep going left until we find the leftmost node
    while (node.left !== null) {
        node = node.left;
    }
    return node;
}

// Recursive approach
findMinRecursive(node = this.root) {
    if (node === null || node.left === null) {
        return node;
    }
    return this.findMinRecursive(node.left);
}

⬆️Find Maximum

Finding the maximum element follows the opposite pattern of finding the minimum. Since all larger values are stored in the right subtree, the maximum element is always the rightmost node in the tree. We traverse right from the root until we reach a node with no right child. Like finding the minimum, this operation also runs in O(h) time.

findMax(node = this.root) {
    if (node === null) return null;
    
    // Keep going right until we find the rightmost node
    while (node.right !== null) {
        node = node.right;
    }
    return node;
}

// Recursive approach
findMaxRecursive(node = this.root) {
    if (node === null || node.right === null) {
        return node;
    }
    return this.findMaxRecursive(node.right);
}

⬅️Find Predecessor

The predecessor of a node is the largest value smaller than the node's value - essentially the previous element in sorted order. There are two cases:Case 1: If the node has a left subtree, the predecessor is the maximum value in that left subtree.Case 2: If there's no left subtree, we need to find the nearest ancestor where our node lies in the right subtree.

findPredecessor(data) {
    let node = this.search(data);
    if (!node) return null;
    
    // Case 1: Node has left subtree
    if (node.left) {
        return this.findMax(node.left);
    }
    
    // Case 2: No left subtree - find ancestor
    let predecessor = null;
    let current = this.root;
    
    while (current !== node) {
        if (data > current.data) {
            predecessor = current;
            current = current.right;
        } else {
            current = current.left;
        }
    }
    return predecessor;
}

➡️Find Successor

The successor of a node is the smallest value larger than the node's value - the next element in sorted order. Similar to predecessor, there are two cases:Case 1: If the node has a right subtree, the successor is the minimum value in that right subtree.Case 2: If there's no right subtree, we find the nearest ancestor where our node lies in the left subtree.

findSuccessor(data) {
    let node = this.search(data);
    if (!node) return null;
    
    // Case 1: Node has right subtree
    if (node.right) {
        return this.findMin(node.right);
    }
    
    // Case 2: No right subtree - find ancestor
    let successor = null;
    let current = this.root;
    
    while (current !== node) {
        if (data < current.data) {
            successor = current;
            current = current.left;
        } else {
            current = current.right;
        }
    }
    return successor;
}