Binary Search Tree Explained with Examples

By Khaled Md Tuhidul Hossain · 2026-01-16 · Algorithms

If you've ever wondered how databases find records so fast, or how your IDE's autocomplete narrows down suggestions as you type, there's a good chance a binary search tree (BST) is doing the heavy lifting somewhere underneath.

The idea is simple. You have a tree where every node follows one rule: everything to its left is smaller, everything to its right is bigger. That single rule gives you fast lookups, inserts, and deletes without needing to shuffle elements around like you would in a sorted array.

Interactive Visualization

Use the controls below to step through the algorithm or let it play automatically.

name: binary-search-tree
input: {"values": [8, 3, 10, 1, 6, 14, 4, 7, 13]}
speed: 600

What Does a BST Look Like?

Here's a BST holding the values 8, 3, 10, 1, 6, 14, 4, 7, 13.

Notice how every left child is less than its parent and every right child is greater. That's the whole invariant. If you can keep that rule intact during inserts and deletes, you've got yourself a working BST.

Inserting a Value

Say we want to insert 5 into the tree above. You start at the root and ask one question at each node: "Am I smaller or bigger?"

Step by step:

1. Compare 5 with root (8). 5 is smaller, go left.
2. Compare 5 with 3. 5 is bigger, go right.
3. Compare 5 with 6. 5 is smaller, go left.
4. Compare 5 with 4. 5 is bigger, go right.
5. No right child exists. Place 5 here.

That's it. You just walked down the tree and found the right spot. No shifting, no re-sorting.

Searching for a Value

Searching works exactly like insertion, except you stop when you find a match instead of placing a new node.

Let's search for 7:

1. Start at 8. 7 < 8, go left.
2. At 3. 7 > 3, go right.
3. At 6. 7 > 6, go right.
4. At 7. Found it.

We visited 4 nodes out of 9. In a balanced tree, you'll visit at most log(n) nodes. Compare that to scanning through an unsorted array where you might check every single element.

Deleting a Node

Deletion is where things get a bit tricky. There are three cases.

Case 1: Node has no children (leaf node). Just remove it. Nothing else to fix.

Case 2: Node has one child. Replace the node with its child. The BST property still holds because the child's subtree was already on the correct side.

Case 3: Node has two children. This is the interesting one. You find the node's in-order successor (the smallest value in its right subtree), copy that value up, then delete the successor from its original position. The successor will have at most one child, so you're back to Case 1 or 2.

Here we deleted node 3. Its in-order successor was 4 (smallest in the right subtree of 3). We replaced 3 with 4 and removed 4 from its old position.

Python Implementation

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


class BinarySearchTree:
    def __init__(self):
        self.root = None

    def insert(self, key):
        if self.root is None:
            self.root = Node(key)
        else:
            self._insert(self.root, key)

    def _insert(self, node, key):
        if key < node.key:
            if node.left is None:
                node.left = Node(key)
            else:
                self._insert(node.left, key)
        elif key > node.key:
            if node.right is None:
                node.right = Node(key)
            else:
                self._insert(node.right, key)
        # Duplicate keys are ignored

    def search(self, key):
        return self._search(self.root, key)

    def _search(self, node, key):
        if node is None:
            return False
        if key == node.key:
            return True
        elif key < node.key:
            return self._search(node.left, key)
        else:
            return self._search(node.right, key)

    def delete(self, key):
        self.root = self._delete(self.root, key)

    def _delete(self, node, key):
        if node is None:
            return None

        if key < node.key:
            node.left = self._delete(node.left, key)
        elif key > node.key:
            node.right = self._delete(node.right, key)
        else:
            # Found the node to delete
            if node.left is None:
                return node.right
            elif node.right is None:
                return node.left

            # Two children: find in-order successor
            successor = self._find_min(node.right)
            node.key = successor.key
            node.right = self._delete(node.right, successor.key)

        return node

    def _find_min(self, node):
        while node.left is not None:
            node = node.left
        return node

    def inorder(self):
        result = []
        self._inorder(self.root, result)
        return result

    def _inorder(self, node, result):
        if node:
            self._inorder(node.left, result)
            result.append(node.key)
            self._inorder(node.right, result)


# Try it out
bst = BinarySearchTree()
for val in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
    bst.insert(val)

print(bst.inorder())       # [1, 3, 4, 6, 7, 8, 10, 13, 14]
print(bst.search(7))       # True
print(bst.search(99))      # False

bst.delete(3)
print(bst.inorder())       # [1, 4, 6, 7, 8, 10, 13, 14]

The recursive approach keeps things clean. Each method passes the problem down to the appropriate subtree until it hits the base case. If you prefer iterative code for production use, you can convert the recursion into a while loop pretty easily.

Time and Space Complexity

So what's the worst case about? If you insert already-sorted data (like 1, 2, 3, 4, 5), your BST degenerates into a linked list. Every node only has a right child. That's why self-balancing trees like AVL and Red-Black trees exist, they rotate nodes to keep the tree roughly balanced.

For the average case though, when data comes in random order, a plain BST performs surprisingly well.

When Should You Use a BST?

Database indexing. Databases use tree-based structures (usually B-trees, which are a generalization of BSTs) to index rows. When you query WHERE age > 25 AND age < 40, the database walks a tree to find that range quickly instead of scanning every row.

Autocomplete and prefix matching. Your IDE's autocomplete builds a tree of known symbols. As you type each character, it narrows down the search space by traversing the relevant branch. A trie is the more specialized version of this, but the concept is rooted in the same tree-based thinking.

Priority scheduling. Operating systems sometimes use BSTs to manage process scheduling. Processes get inserted with a priority value, and the scheduler can find the highest-priority process by walking to the rightmost node.

Sorted output on the fly. If you need to maintain a collection that stays sorted as elements come and go, a BST gives you that without re-sorting. An in-order traversal always produces elements in sorted order.

Quick Recap

BSTs are one of those data structures that click once you see the pattern. Left means smaller, right means bigger. Every operation just follows that rule down the tree. The tricky part is deletion with two children, but once you understand the in-order successor trick, that clicks too.

If your data is reasonably random, a plain BST works great. If you're worried about worst-case performance, look into AVL trees or Red-Black trees, they're BSTs with automatic balancing built in.