Binary Search Tree Explained — Insert, Search, Delete & Real-World Use Cases

Every app that lets you search, filter, or sort data under the hood needs a structure that can find things fast. Arrays are fine when your data never changes, but the moment you need to insert a new user, delete an expired record, or search a million entries in milliseconds, a flat list becomes a bottleneck. Binary Search Trees were designed precisely for that intersection of speed and flexibility — they keep your data permanently sorted as you insert it, so searching never degrades into a slow linear scan.

The core problem a BST solves is the trade-off between lookup speed and the cost of keeping data ordered. A sorted array gives you fast O(log n) binary search, but inserting into the middle requires shifting every element to the right — painful at scale. A linked list inserts in O(1) but forces you to scan from the start every time you search. A BST gives you the best of both: O(log n) search AND O(log n) insertion, because the tree's shape itself encodes the sorted order.

By the end of this article you'll be able to implement a fully functional BST from scratch in Java — including insertion, recursive and iterative search, and the tricky three-case deletion algorithm. You'll understand when a BST is the right tool, when it isn't, and you'll have the vocabulary to talk about it confidently in a technical interview.

What is Binary Search Tree (BST)? — Plain English

A Binary Search Tree is a binary tree where every node satisfies the BST property: all values in the left subtree are strictly less than the node, and all values in the right subtree are strictly greater. This ordering makes search, insert, and delete O(log n) in a balanced tree.

Real-world use: ordered dictionaries (Java's TreeMap, C++'s std::map), database index B-trees, and any application needing fast sorted access.

How Binary Search Tree (BST) Works — Step by Step

Search (O(log n) balanced, O(n) worst-case skewed): 1. Start at root. 2. If target == node.val: found. 3. If target < node.val: recurse left. 4. If target > node.val: recurse right. 5. If None reached: not found.

Insert (O(log n) average): 1. Search as above. When you reach None, insert the new node there.

Delete (O(log n) average): 1. Find the node. 2. No children: simply remove. 3. One child: replace node with its child. 4. Two children: replace value with in-order successor (smallest in right subtree). Delete the successor.

Worked Example — Tracing the Algorithm

BST operations on [8, 3, 10, 1, 6, 14, 4, 7].

Build: Insert 8: root=8. Insert 3: 3<8, go left. 8.left=3. Insert 10: 10>8, go right. 8.right=10. Insert 1: 1<8→left(3), 1<3→left. 3.left=1. Insert 6: 6<8→left(3), 6>3→right. 3.right=6. Insert 14: 14>8→right(10), 14>10→right. 10.right=14. Insert 4: <8→3, >3→6, <6→left. 6.left=4. Insert 7: <8→3, >3→6, >6→right. 6.right=7.

Search for 6: 6<8→left. 6>3→right. 6==6. Found!

Delete 3 (two children: 1 and 6): In-order successor = smallest in right subtree = 4. Replace 3's value with 4. Delete 4 from right subtree (leaf deletion). Result: 4 takes 3's position.

Implementation

The BST node stores a value and left/right child pointers. Search walks left or right based on comparison and returns True when the target equals the current node. Insert follows the same path and creates a leaf when it reaches None. Delete handles three cases: no children (remove node), one child (splice out), two children (replace with in-order successor then delete the successor from the right subtree). All operations are O(h) where h is height — O(log n) average, O(n) worst case for skewed trees.

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

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

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

def inorder(root, result=None):
    if result is None: result = []
    if root:
        inorder(root.left, result)
        result.append(root.val)
        inorder(root.right, result)
    return result

root = None
for v in [8,3,10,1,6,14,4,7]:
    root = insert(root, v)
print('Inorder:', inorder(root))  # sorted
print('Search 6:', search(root, 6))
print('Search 5:', search(root, 5))

Frequently Asked Questions