Binary Search Tree (BST)

What is a BST?

A Binary Search Tree (BST) is a binary tree with a special ordering property: for every node, all values in the left subtree are smaller and all values in the right subtree are larger. This property enables efficient search, insert, and delete operations.

Operation	Average (balanced)	Worst (skewed)
Search	O(log n)	O(n)
Insert	O(log n)	O(n)
Delete	O(log n)	O(n)
Min/Max	O(log n)	O(n)

Key insight: Inorder traversal of a BST always gives elements in sorted ascending order.

BST â€” Insert, Search, Delete, Min/Max

#include <iostream>
using namespace std;

struct Node {
    int val;
    Node *left, *right;
    Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

Node* insert(Node* root, int val) {
    if (!root) return new Node(val);
    if (val < root->val) root->left  = insert(root->left,  val);
    else if (val > root->val) root->right = insert(root->right, val);
    return root;  // duplicate: ignore
}

bool search(Node* root, int val) {
    if (!root) return false;
    if (val == root->val) return true;
    if (val < root->val) return search(root->left, val);
    return search(root->right, val);
}

Node* findMin(Node* root) {
    while (root->left) root = root->left;
    return root;
}

Node* deleteNode(Node* root, int val) {
    if (!root) return nullptr;
    if (val < root->val) root->left  = deleteNode(root->left,  val);
    else if (val > root->val) root->right = deleteNode(root->right, val);
    else {
        if (!root->left)  return root->right;
        if (!root->right) return root->left;
        // Two children: replace with inorder successor (min of right subtree)
        Node* successor = findMin(root->right);
        root->val = successor->val;
        root->right = deleteNode(root->right, successor->val);
    }
    return root;
}

void inorder(Node* root) {
    if (!root) return;
    inorder(root->left);
    cout << root->val << " ";
    inorder(root->right);
}

int main() {
    Node* root = nullptr;
    for (int x : {5, 3, 7, 1, 4, 6, 8}) root = insert(root, x);

    cout << "Inorder: "; inorder(root); cout << endl;  // 1 3 4 5 6 7 8
    cout << boolalpha << "Search 4: " << search(root, 4) << endl;  // true
    cout << "Search 9: " << search(root, 9) << endl;  // false
    cout << "Min: " << findMin(root)->val << endl;  // 1

    root = deleteNode(root, 3);
    cout << "After delete 3: "; inorder(root); cout << endl;  // 1 4 5 6 7 8
    return 0;
}

public class BST {
    static class Node {
        int val; Node left, right;
        Node(int v) { val = v; }
    }

    static Node insert(Node root, int val) {
        if (root == null) return new Node(val);
        if (val < root.val) root.left  = insert(root.left,  val);
        else if (val > root.val) root.right = insert(root.right, val);
        return root;
    }

    static boolean search(Node root, int val) {
        if (root == null) return false;
        if (val == root.val) return true;
        return val < root.val ? search(root.left, val) : search(root.right, val);
    }

    static int findMin(Node root) {
        while (root.left != null) root = root.left;
        return root.val;
    }

    static Node delete(Node root, int val) {
        if (root == null) return null;
        if (val < root.val) root.left  = delete(root.left,  val);
        else if (val > root.val) root.right = delete(root.right, val);
        else {
            if (root.left  == null) return root.right;
            if (root.right == null) return root.left;
            root.val = findMin(root.right);
            root.right = delete(root.right, root.val);
        }
        return root;
    }

    static void inorder(Node root) {
        if (root == null) return;
        inorder(root.left);
        System.out.print(root.val + " ");
        inorder(root.right);
    }

    public static void main(String[] args) {
        Node root = null;
        for (int x : new int[]{5,3,7,1,4,6,8}) root = insert(root, x);
        System.out.print("Inorder: "); inorder(root); System.out.println();
        System.out.println("Search 4: " + search(root, 4));  // true
        System.out.println("Min: " + findMin(root));          // 1
        root = delete(root, 3);
        System.out.print("After delete 3: "); inorder(root); System.out.println();
    }
}

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def insert(root, val):
    if not root: return Node(val)
    if val < root.val:   root.left  = insert(root.left,  val)
    elif val > root.val: root.right = insert(root.right, val)
    return root

def search(root, val):
    if not root: return False
    if val == root.val: return True
    return search(root.left, val) if val < root.val else search(root.right, val)

def find_min(root):
    while root.left: root = root.left
    return root.val

def delete(root, val):
    if not root: return None
    if val < root.val:   root.left  = delete(root.left,  val)
    elif val > root.val: root.right = delete(root.right, val)
    else:
        if not root.left:  return root.right
        if not root.right: return root.left
        # Replace with inorder successor
        root.val = find_min(root.right)
        root.right = delete(root.right, root.val)
    return root

def inorder(root):
    if not root: return []
    return inorder(root.left) + [root.val] + inorder(root.right)

root = None
for x in [5, 3, 7, 1, 4, 6, 8]:
    root = insert(root, x)

print("Inorder:", inorder(root))    # [1, 3, 4, 5, 6, 7, 8]
print("Search 4:", search(root, 4)) # True
print("Min:", find_min(root))       # 1
root = delete(root, 3)
print("After delete 3:", inorder(root))  # [1, 4, 5, 6, 7, 8]

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

function insert(root, val) {
    if (!root) return new Node(val);
    if (val < root.val)      root.left  = insert(root.left,  val);
    else if (val > root.val) root.right = insert(root.right, val);
    return root;
}

function search(root, val) {
    if (!root) return false;
    if (val === root.val) return true;
    return val < root.val ? search(root.left, val) : search(root.right, val);
}

function findMin(root) {
    while (root.left) root = root.left;
    return root.val;
}

function deleteNode(root, val) {
    if (!root) return null;
    if (val < root.val)      root.left  = deleteNode(root.left,  val);
    else if (val > root.val) root.right = deleteNode(root.right, val);
    else {
        if (!root.left)  return root.right;
        if (!root.right) return root.left;
        root.val = findMin(root.right);
        root.right = deleteNode(root.right, root.val);
    }
    return root;
}

function inorder(root, result = []) {
    if (!root) return result;
    inorder(root.left, result);
    result.push(root.val);
    inorder(root.right, result);
    return result;
}

let root = null;
for (const x of [5,3,7,1,4,6,8]) root = insert(root, x);
console.log("Inorder:", inorder(root));    // [1,3,4,5,6,7,8]
console.log("Search 4:", search(root, 4)); // true
console.log("Min:", findMin(root));        // 1
root = deleteNode(root, 3);
console.log("After delete 3:", inorder(root)); // [1,4,5,6,7,8]

Previous Next

Binary Search Tree (BST)

What is a BST?

Ready to Level Up Your Skills?