Binary Search Trees Explained

A binary search tree (BST) is a binary tree with one extra rule: for every node, all values in its left subtree are smaller, and all values in its right subtree are larger. This ordering lets you discard half the remaining tree at each step while searching, giving O(log n) lookups when the tree is balanced — the same divide-and-conquer power as binary search, but on a structure you can insert into and delete from cheaply.

The ordering rule

Picture searching for a value. You start at the root. If your target is smaller, you go left; if larger, you go right; if equal, you found it. Because each comparison eliminates an entire subtree, you only follow a single path from root to leaf. In a balanced tree that path has length about log2(n), so searching a million-node tree takes only around 20 comparisons.

The same rule guides insertion and deletion, so all three core operations share the O(log n) cost on a balanced tree.

Searching and inserting in a BST

#include <iostream>
using namespace std;

struct Node {
    int key;
    Node* left;
    Node* right;
    Node(int k) : key(k), left(nullptr), right(nullptr) {}
};

// Insert a key, following the left-smaller, right-larger rule.
// On a balanced tree this is O(log n); on a degenerate one, O(n).
Node* insert(Node* root, int key) {
    if (root == nullptr) {
        return new Node(key);     // empty spot found: place the key here
    }
    if (key < root->key) {
        root->left = insert(root->left, key);   // go left for smaller keys
    } else if (key > root->key) {
        root->right = insert(root->right, key); // go right for larger keys
    }
    // equal keys are ignored here (no duplicates)
    return root;
}

// Search for a key. Returns true if present. O(log n) when balanced.
bool search(Node* root, int key) {
    while (root != nullptr) {
        if (key == root->key) return true; // found it
        root = (key < root->key) ? root->left : root->right; // pick a side
    }
    return false; // ran off the tree without finding it
}

int main() {
    Node* root = nullptr;
    int values[] = {50, 30, 70, 20, 40, 60, 80};
    for (int v : values) {
        root = insert(root, v);
    }
    cout << search(root, 40) << endl; // 1 (found)
    cout << search(root, 45) << endl; // 0 (not found)
    return 0;
}

Each step of the search moves down one level, so the work is proportional to the tree's height, not its total size.

Balance is everything

The O(log n) promise only holds while the tree stays roughly balanced. Insert keys in sorted order — 10, 20, 30, 40 — and every node ends up with only a right child. The tree degenerates into a straight line, exactly like a linked list, and search becomes O(n).

Self-balancing variants such as AVL trees and red-black trees solve this by rotating nodes during insertion and deletion to keep the height near log n. They are more complex, but they guarantee the logarithmic bound no matter the insertion order.

Why use a BST

A BST gives you sorted data with fast search, insertion, and deletion all at once. An in-order traversal of a BST visits keys in ascending order for free. Where a sorted array gives O(log n) search but O(n) insertion, a balanced BST gives O(log n) for both — useful when the data set keeps changing.

Common mistakes

• Ignoring balance. Building a BST from already-sorted input creates the worst case. If your input might be sorted, shuffle it or use a self-balancing tree.
• Mishandling deletion. Removing a node with two children requires replacing it with its in-order successor (or predecessor). Forgetting this breaks the ordering rule.
• Allowing inconsistent duplicates. Decide a rule for equal keys (reject, or always go one direction) and apply it everywhere, or searches will miss values.
• Confusing a BST with any binary tree. A plain binary tree has no ordering. Only the left-smaller, right-larger invariant makes search fast.
• Assuming worst case is rare. Sorted or nearly-sorted real-world data is common, so the degenerate case happens more often than beginners expect.

FAQ

Is a balanced BST always O(log n)? A self-balancing BST guarantees O(log n) for search, insert, and delete. A plain BST is O(log n) only on average and degrades to O(n) when unbalanced.

BST or hash table? A hash table gives faster average lookups (close to O(1)) but no sorted order. A BST keeps data ordered and supports range queries. Choose based on whether you need ordering.

Keep learning

Make sure you understand Trees Explained first, compare lookup speeds in Hashing & Hash Tables, and browse the full DSA hub.

Want to implement BSTs and balancing with instructor feedback in Jalgaon? Join the waitlist for our Data Structures & Algorithms course.