iwantcoding.com
🔥 Daily 👥 Rooms 🏆 Top Log in Sign up

Binary Search Trees

By · Reviewed & last updated · Part of Data Structures & Algorithms

A binary search tree (BST) keeps an ordering invariant: every node’s left subtree is smaller, its right subtree is larger. Lookups, inserts, deletes are O(log n) on average, O(n) if unbalanced. Self-balancing variants (AVL, red-black) keep it logarithmic always.

Insert, search, delete

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

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

// 2) Search
function search(root, val) {
    while (root && root.val !== val) {
        root = val < root.val ? root.left : root.right;
    }
    return root;
}

// 3) Min / Max
function min(root) { while (root.left)  root = root.left;  return root; }
function max(root) { while (root.right) root = root.right; return root; }

// 4) Delete — three cases
function remove(root, val) {
    if (!root) return null;
    if (val < root.val)      root.left  = remove(root.left,  val);
    else if (val > root.val) root.right = remove(root.right, val);
    else {
        // 4a) Leaf
        if (!root.left && !root.right) return null;
        // 4b) One child
        if (!root.left)  return root.right;
        if (!root.right) return root.left;
        // 4c) Two children — replace with in-order successor
        const succ = min(root.right);
        root.val = succ.val;
        root.right = remove(root.right, succ.val);
    }
    return root;
}

// 5) Valid BST check
function isBST(root, lo = -Infinity, hi = Infinity) {
    if (!root) return true;
    if (root.val <= lo || root.val >= hi) return false;
    return isBST(root.left, lo, root.val) && isBST(root.right, root.val, hi);
}

// 6) In-order traversal — emits values SORTED for any BST
function inorder(root, out = []) {
    if (!root) return out;
    inorder(root.left,  out);
    out.push(root.val);
    inorder(root.right, out);
    return out;
}

Why it matters

In real code, reach for an ordered map / sorted set (TreeMap in Java, SortedDict in Python, BTreeMap in Rust) instead of hand-rolling a BST. Hand-rolled is for interviews and learning.

Tip: Tweak the snippet with Try it Yourself », then sit the quiz at the bottom of the page.

Example

Example
function insert(root, v) {
    if (!root) return new TreeNode(v);
    if (v < root.v) root.left  = insert(root.left, v);
    else            root.right = insert(root.right, v);
    return root;
}
Try it Yourself »

Discussion

Loading…