Binary Search Tree

How BST Works

A Binary Search Tree is a rooted binary tree that satisfies the BST property: for every node N, all values in N's left subtree are strictly less than N's value, and all values in N's right subtree are strictly greater. This invariant is maintained after every insert and delete operation.

The key operations on a BST are:

Search: Start at the root. If the target equals the current node, you are done. If it is smaller, recurse left; if larger, recurse right. Each comparison eliminates roughly half the remaining nodes, yielding O(log n) average time.
Insert: Follow the same path as search until you reach a null child pointer. Place the new node there. The tree grows by one leaf each time.
Delete: There are three cases to handle:
- Leaf node: Simply remove it.
- One child: Replace the node with its single child.
- Two children: Find the inorder successor (smallest node in the right subtree), copy its value into the node being deleted, then delete the successor from the right subtree.
Inorder traversal: Visit left subtree, then the node, then right subtree. This produces values in sorted (ascending) order.
Preorder traversal: Visit the node first, then left subtree, then right subtree. Useful for creating a copy of the tree.

Important caveat: If elements are inserted in sorted order, the BST degenerates into a linked list, and all operations become O(n). Self-balancing trees such as AVL trees and Red-Black trees address this problem by automatically rebalancing after mutations.

Interactive Visualization

Explore BST operations below. Red nodes are currently being visited or compared, and green nodes have been found or just processed. Enter a value and choose an operation to watch the BST algorithm step by step.

Binary Search Tree with values [50, 30, 70, 20, 40, 60, 80]. Use the buttons below to perform operations.

Speed No steps

Value:

Code Implementation

Below are BST insert and search implementations in three languages. The recursive approach mirrors the tree's own structure and is the most natural way to express BST operations.

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


def insert(root, val):
    """Insert a value into the BST and return the root."""
    if root is None:
        return BSTNode(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):
    """Return the node containing val, or None if not found."""
    if root is None or root.val == val:
        return root
    if val < root.val:
        return search(root.left, val)
    return search(root.right, val)


def inorder(root):
    """Return a list of values in sorted (inorder) order."""
    if root is None:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)


# Example usage
root = None
for v in [50, 30, 70, 20, 40, 60, 80]:
    root = insert(root, v)

print(inorder(root))         # [20, 30, 40, 50, 60, 70, 80]
print(search(root, 40))      # <BSTNode object>
print(search(root, 99))      # None

class BSTNode {
    int val;
    BSTNode left, right;

    BSTNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

public class BST {
    private BSTNode root;

    /** Insert a value into the BST. */
    public void insert(int val) {
        root = insertRec(root, val);
    }

    private BSTNode insertRec(BSTNode node, int val) {
        if (node == null) return new BSTNode(val);
        if (val < node.val)
            node.left = insertRec(node.left, val);
        else if (val > node.val)
            node.right = insertRec(node.right, val);
        return node;
    }

    /** Search for a value. Returns true if found. */
    public boolean search(int val) {
        return searchRec(root, val);
    }

    private boolean searchRec(BSTNode node, int val) {
        if (node == null) return false;
        if (val == node.val) return true;
        if (val < node.val) return searchRec(node.left, val);
        return searchRec(node.right, val);
    }

    public static void main(String[] args) {
        BST tree = new BST();
        int[] values = {50, 30, 70, 20, 40, 60, 80};
        for (int v : values) tree.insert(v);

        System.out.println(tree.search(40));  // true
        System.out.println(tree.search(99));  // false
    }
}

#include <iostream>
using namespace std;

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

/** Insert a value into the BST and return the root. */
BSTNode* insert(BSTNode* root, int val) {
    if (!root) return new BSTNode(val);
    if (val < root->val)
        root->left = insert(root->left, val);
    else if (val > root->val)
        root->right = insert(root->right, val);
    return root;
}

/** Search for a value. Returns the node or nullptr. */
BSTNode* search(BSTNode* root, int val) {
    if (!root || root->val == val) return root;
    if (val < root->val) return search(root->left, val);
    return search(root->right, val);
}

/** Print inorder traversal. */
void inorder(BSTNode* root) {
    if (!root) return;
    inorder(root->left);
    cout << root->val << " ";
    inorder(root->right);
}

int main() {
    BSTNode* root = nullptr;
    int values[] = {50, 30, 70, 20, 40, 60, 80};
    for (int v : values) root = insert(root, v);

    inorder(root);  // 20 30 40 50 60 70 80
    cout << endl;

    cout << (search(root, 40) ? "Found" : "Not found") << endl;  // Found
    cout << (search(root, 99) ? "Found" : "Not found") << endl;  // Not found
    return 0;
}

Complexity Analysis

BST operation performance depends on the height of the tree. For a balanced tree with n nodes, the height is O(log n), giving logarithmic performance. In the worst case (a degenerate/skewed tree), the height becomes O(n), and every operation degrades to linear time.

Operation	Average Case	Worst Case	Description
Search	O(log n)	O(n)	Balanced tree halves search space each step; skewed tree traverses all nodes
Insert	O(log n)	O(n)	Follows search path to find insertion point at a leaf position
Delete	O(log n)	O(n)	Search for node plus possible successor lookup, both bounded by tree height
Space	O(n)		Each of the n values is stored in exactly one node

Self-balancing variants like AVL trees and Red-Black trees guarantee O(log n) height through rotations after insertions and deletions, ensuring worst-case O(log n) for all operations. In practice, randomly ordered insertions produce a tree with expected height of about 1.39 log₂(n), which is close to optimal.

Quiz

Test your understanding of binary search trees with these questions.

Q1. What is the BST property?

Every node has exactly two children

The tree is always perfectly balanced

For every node, all left-subtree values are less and all right-subtree values are greater

Parent nodes are always larger than child nodes

The BST property states that for any node N, every value in its left subtree is strictly less than N's value, and every value in its right subtree is strictly greater. This enables efficient searching by eliminating half the tree at each step. A BST does not require perfect balance or exactly two children per node.

Q2. What traversal of a BST produces values in sorted ascending order?

Preorder (Node, Left, Right)

Inorder (Left, Node, Right)

Postorder (Left, Right, Node)

Level-order (BFS)

Inorder traversal visits the left subtree first (all smaller values), then the current node, then the right subtree (all larger values). Because of the BST property, this produces values in sorted ascending order. Preorder and postorder produce different orderings, and level-order visits nodes breadth-first which does not guarantee sorted output.

Q3. When deleting a node with two children from a BST, what is the standard approach?

Remove the node and attach both subtrees to its parent

Replace the node with its left child

Rebuild the entire tree without the deleted value

Replace the node's value with its inorder successor, then delete the successor

When a node has two children, we find its inorder successor (the smallest node in its right subtree), copy that value into the node being deleted, and then recursively delete the successor from the right subtree. The successor is guaranteed to have at most one child (no left child), making it simpler to remove. This maintains the BST property.

Q4. If you insert the values [1, 2, 3, 4, 5] into an initially empty BST in that order, what is the height of the resulting tree?

4 (the tree degenerates into a right-skewed chain)

2 (the tree is balanced)

3

5

When values are inserted in sorted order, each new value is always greater than the current root, so it goes to the right child, then the right child of that, and so on. The result is a right-skewed chain: 1 → 2 → 3 → 4 → 5, with height 4 (counting edges from root to deepest leaf). This is the worst-case scenario for a BST and why self-balancing trees exist.

Q5. What is the worst-case time complexity of searching in a BST with n nodes?

O(1)

O(log n)

O(n)

O(n log n)

In the worst case, a BST can degenerate into a linked list (e.g., when elements are inserted in sorted order). In this situation, the height of the tree equals n - 1, and a search must traverse every node, resulting in O(n) time. On average with random insertions, the height is O(log n), but the worst case is linear. Self-balancing BSTs guarantee O(log n) worst-case search.

How BST Works

Interactive Visualization

Code Implementation

Complexity Analysis

Quiz

Keyboard Shortcuts