Binary Search Trees

Compare the target with the current node. Go left if smaller, right if larger. Repeat until found or null.

function searchBST(root, target) {
    if (!root) return null;
    if (target === root.val) return root;
    if (target < root.val) return searchBST(root.left, target);
    return searchBST(root.right, target);
}

// Iterative version:
function searchBSTIterative(root, target) {
    while (root && root.val !== target) {
        root = target < root.val ? root.left : root.right;
    }
    return root;
}

Time: O(h) where h is the height — O(log n) for balanced, O(n) for skewed.

Navigate the tree like a search. When you reach a null position, insert the new node there.

function insertBST(root, val) {
    if (!root) return new TreeNode(val);
    if (val < root.val) {
        root.left = insertBST(root.left, val);
    } else {
        root.right = insertBST(root.right, val);
    }
    return root;
}

// Insert 5 into:
//     8            8
//    / \   =>    / \
//   3   10      3   10
//              / \
//             ?   6
//                /
//               5   (new node)

Time: O(h)  |  Space: O(h) for recursive, O(1) for iterative.

Three cases when deleting a node:

• Leaf node: Simply remove it.
• One child: Replace with the child.
• Two children: Replace with the inorder successor (smallest in right subtree) or inorder predecessor.

function deleteBST(root, val) {
    if (!root) return null;
    if (val < root.val) root.left = deleteBST(root.left, val);
    else if (val > root.val) root.right = deleteBST(root.right, val);
    else {
        if (!root.left) return root.right;
        if (!root.right) return root.left;
        // Two children: find inorder successor
        let successor = root.right;
        while (successor.left) successor = successor.left;
        root.val = successor.val;
        root.right = deleteBST(root.right, successor.val);
    }
    return root;
}

Time: O(h)  |  Space: O(h)

Check that each node's value falls within a valid range (min, max). The range narrows as you traverse.

function isValidBST(node, min = -Infinity, max = Infinity) {
    if (!node) return true;
    if (node.val <= min || node.val >= max) return false;
    return isValidBST(node.left, min, node.val) &&
           isValidBST(node.right, node.val, max);
}

// OR use inorder traversal — it should produce sorted order:
function isValidBSTInorder(root) {
    let prev = -Infinity;
    function inorder(node) {
        if (!node) return true;
        if (!inorder(node.left)) return false;
        if (node.val <= prev) return false;
        prev = node.val;
        return inorder(node.right);
    }
    return inorder(root);
}

Time: O(n)  |  Space: O(h)

The inorder successor is the node with the smallest value greater than the given node.

• If right subtree exists: The successor is the leftmost node in the right subtree.
• If no right subtree: Traverse from root, tracking the last node where you went left.

function inorderSuccessor(root, target) {
    // Case 1: right subtree exists
    if (target.right) {
        let node = target.right;
        while (node.left) node = node.left;
        return node;
    }
    // Case 2: go up — find nearest ancestor for which target is in left subtree
    let successor = null;
    let curr = root;
    while (curr) {
        if (target.val < curr.val) {
            successor = curr;
            curr = curr.left;
        } else {
            curr = curr.right;
        }
    }
    return successor;
}

Time: O(h)  |  Space: O(1)

Perform an inorder traversal (which visits nodes in sorted order) and return the kth element.

function kthSmallest(root, k) {
    let count = 0;
    let result = null;

    function inorder(node) {
        if (!node || result !== null) return;
        inorder(node.left);
        count++;
        if (count === k) { result = node.val; return; }
        inorder(node.right);
    }

    inorder(root);
    return result;
}
//       5
//      / \
//     3   6
//    / \
//   2   4
// kthSmallest(root, 3) => 4

Time: O(h + k)  |  Space: O(h)

Use the middle element as root, and recursively build left and right subtrees from the two halves.

function sortedArrayToBST(nums) {
    if (nums.length === 0) return null;

    function build(left, right) {
        if (left > right) return null;
        const mid = Math.floor((left + right) / 2);
        const node = new TreeNode(nums[mid]);
        node.left = build(left, mid - 1);
        node.right = build(mid + 1, right);
        return node;
    }

    return build(0, nums.length - 1);
}
// [1,2,3,4,5,6,7] =>
//       4
//      / \
//     2   6
//    / \ / \
//   1  3 5  7

Time: O(n)  |  Space: O(log n) recursion stack. The resulting tree is height-balanced.

Both support efficient lookup, but they serve different needs:

• BST advantages: Maintains sorted order, supports range queries, finds min/max in O(h), in-order traversal gives sorted output.
• Hash table advantages: O(1) average lookup/insert/delete (vs O(log n) for balanced BST), simpler for key-value storage.

Use a BST when order matters; use a hash table when speed is the priority.

Self-balancing BSTs automatically maintain O(log n) height after insertions and deletions.

• AVL Tree: Strictly balanced — height difference between left/right subtrees is at most 1. Uses rotations (left, right, left-right, right-left) to rebalance. Faster lookups.
• Red-Black Tree: Each node is red or black with specific coloring rules. Less strictly balanced than AVL but fewer rotations on insert/delete. Used in Java's TreeMap, C++ std::map.

// AVL Rotation concept (Right Rotation):
//     y          x
//    / \        / \
//   x   C  =>  A   y
//  / \            / \
// A   B          B   C

// All operations guaranteed O(log n):
// Search: O(log n)
// Insert: O(log n) + O(1) rotations (AVL: max 2)
// Delete: O(log n) + O(log n) rotations (AVL)

In practice, most languages provide balanced BST implementations in their standard libraries.

In-order traversal of a BST produces values in sorted ascending order. Simply return the kth value visited.

function kthSmallest(root, k) {
    let count = 0, result = null;
    function inorder(node) {
        if (!node || result !== null) return;
        inorder(node.left);
        if (++count === k) { result = node.val; return; }
        inorder(node.right);
    }
    inorder(root);
    return result;
}
// BST: 3(1(null,2), 4), k=1  => Output: 1  (smallest)
// BST: 5(3(2,4), 6), k=3      => Output: 4

Time: O(H + k) where H is height  |  Space: O(H)

Perform in-order traversal. In a valid BST in-order is sorted — the two swapped nodes will appear as anomalies (first: prev > curr; second: last such curr). Swap their values back.

function recoverTree(root) {
    let first = null, second = null, prev = null;
    function inorder(node) {
        if (!node) return;
        inorder(node.left);
        if (prev && prev.val > node.val) {
            if (!first) first = prev; // first anomaly
            second = node;            // always update second
        }
        prev = node;
        inorder(node.right);
    }
    inorder(root);
    [first.val, second.val] = [second.val, first.val]; // swap back
}
// BST with 3 and 1 swapped: [3,1] <- should be [1,3]
// After recover: BST is valid again

Time: O(n)  |  Space: O(h)

Use divide and conquer. The middle element becomes the root; recursively build left and right subtrees from the two halves.

function sortedArrayToBST(nums) {
    function build(left, right) {
        if (left > right) return null;
        const mid = Math.floor((left + right) / 2);
        const node = { val: nums[mid] };
        node.left  = build(left, mid - 1);
        node.right = build(mid + 1, right);
        return node;
    }
    return build(0, nums.length - 1);
}
// Input: [-10,-3,0,5,9]
// Output: balanced BST with root=0, left=-3(-10), right=9(5)
// Input: [1,3]  => root=1(null, 3) or root=3(1, null) both valid

Time: O(n)  |  Space: O(log n) stack, O(n) output

Pass min/max bounds down the recursion. At each node, its value must be strictly within the allowed range, which narrows as you go deeper.

function isValidBST(root, min = -Infinity, max = Infinity) {
    if (!root) return true;
    if (root.val <= min || root.val >= max) return false;
    return isValidBST(root.left,  min,      root.val)
        && isValidBST(root.right, root.val, max);
}
// Valid BST:   2(1, 3)             => true
// Invalid:     5(1, 4(3,6))        => false (4 < 5 but right child)
// Edge case:   2(2, null)          => false (equal not allowed)

Time: O(n)  |  Space: O(h)

The inorder successor is the leftmost node in the right subtree (if it exists), or the closest ancestor for which the target is in the left subtree.

function inorderSuccessor(root, p) {
    let successor = null;
    while (root) {
        if (p.val < root.val) {
            successor = root; // candidate: current node
            root = root.left; // try to find closer
        } else {
            root = root.right; // p is in right subtree
        }
    }
    return successor;
}
// BST: 5(3(2,4), 6)
// inorderSuccessor(node_3) => node_4
// inorderSuccessor(node_4) => node_5
// inorderSuccessor(node_6) => null (no successor)

Time: O(h)  |  Space: O(1)

Use BST properties to prune subtrees: skip the left subtree if current < low, skip the right if current > high. Otherwise sum and recurse both.

function rangeSumBST(root, low, high) {
    if (!root) return 0;
    if (root.val < low)  return rangeSumBST(root.right, low, high);
    if (root.val > high) return rangeSumBST(root.left,  low, high);
    return root.val
        + rangeSumBST(root.left,  low, high)
        + rangeSumBST(root.right, low, high);
}
// BST: 10(5(3,7), 15(13,18))
// rangeSumBST(root, 7, 15) => Output: 32  (7 + 10 + 15)
// rangeSumBST(root, 6, 10) => Output: 17  (7 + 10)

Time: O(n) worst, O(log n + k) average with pruning  |  Space: O(h)

Three cases: (1) No children — remove directly. (2) One child — replace with child. (3) Two children — replace value with in-order successor (leftmost of right subtree), then delete successor.

function deleteNode(root, key) {
    if (!root) return null;
    if (key < root.val) {
        root.left  = deleteNode(root.left,  key);
    } else if (key > root.val) {
        root.right = deleteNode(root.right, key);
    } else {
        // Found node to delete
        if (!root.left)  return root.right;
        if (!root.right) return root.left;
        // Two children: find inorder successor
        let minNode = root.right;
        while (minNode.left) minNode = minNode.left;
        root.val   = minNode.val;
        root.right = deleteNode(root.right, minNode.val);
    }
    return root;
}
// BST: 5(3(2,4), 6), delete 3 => 5(4(2), 6)

Time: O(h)  |  Space: O(h)

Use BST ordering: if both p and q are less than current, go left; if both greater, go right; otherwise current is the LCA.

function lowestCommonAncestorBST(root, p, q) {
    while (root) {
        if (p.val < root.val && q.val < root.val) {
            root = root.left;
        } else if (p.val > root.val && q.val > root.val) {
            root = root.right;
        } else {
            return root; // split point = LCA
        }
    }
    return null;
}
// BST: 6(2(0,4(3,5)), 8(7,9))
// LCA(2, 8) => node 6
// LCA(2, 4) => node 2

Time: O(h)  |  Space: O(1) iterative

Recursively: if current < low, return trimmed right subtree. If current > high, return trimmed left subtree. Otherwise trim both children.

function trimBST(root, low, high) {
    if (!root) return null;
    if (root.val < low)  return trimBST(root.right, low, high);
    if (root.val > high) return trimBST(root.left,  low, high);
    root.left  = trimBST(root.left,  low, high);
    root.right = trimBST(root.right, low, high);
    return root;
}
// BST: 3(0(null,2(1)),4), low=1, high=3
// Output trimmed tree: 3(2(1), null)

Time: O(n)  |  Space: O(h)

In-order traversal builds the nodes in sorted order. Maintain a prev pointer to link each node to the previous as a doubly linked list.

function treeToDoublyList(root) {
    if (!root) return null;
    let head = null, prev = null;
    function inorder(node) {
        if (!node) return;
        inorder(node.left);
        if (prev) { prev.right = node; node.left = prev; }
        else head = node; // leftmost node = head
        prev = node;
        inorder(node.right);
    }
    inorder(root);
    // Make circular
    prev.right = head; head.left = prev;
    return head;
}
// BST: 4(2(1,3), 5)
// Output: 1 <-> 2 <-> 3 <-> 4 <-> 5 (circular)

Time: O(n)  |  Space: O(h)

This equals the nth Catalan number: C(n) = ΣC(i-1)×C(n-i) for i from 1 to n, with C(0)=C(1)=1.

function numTrees(n) {
    const dp = new Array(n + 1).fill(0);
    dp[0] = 1; dp[1] = 1;
    for (let i = 2; i <= n; i++) {
        for (let j = 1; j <= i; j++) {
            dp[i] += dp[j - 1] * dp[i - j]; // j as root
        }
    }
    return dp[n];
}
// Input: n=3  => Output: 5
// Input: n=4  => Output: 14
// Input: n=1  => Output: 1

Time: O(n²)  |  Space: O(n)

Floor: largest BST value ≤ target. Ceiling: smallest BST value ≥ target. Both use BST ordering to navigate and track candidate values.

function floorInBST(root, target) {
    let floor = null;
    while (root) {
        if (root.val === target) return root.val;
        if (root.val < target) { floor = root.val; root = root.right; }
        else root = root.left;
    }
    return floor;
}
function ceilingInBST(root, target) {
    let ceil = null;
    while (root) {
        if (root.val === target) return root.val;
        if (root.val > target) { ceil = root.val; root = root.left; }
        else root = root.right;
    }
    return ceil;
}
// BST: 8(4(2,6), 10), target=5
// floorInBST => 4    ceilingInBST => 6

Time: O(h)  |  Space: O(1)