AlgoMaster Logo

Introduction to BST

High Priority10 min readUpdated June 30, 2026
Listen to this chapter
Unlock Audio

Binary Search Tree

Binary Search Tree (BST) is a data structure that combines the hierarchical structure of binary tree with the ordering of a sorted list, and the efficiency of binary search.

This structure makes searching, inserting, and deleting elements efficient, often in O(log n) time when the tree is balanced.

BSTs (and their self-balancing variants like AVL and red-black trees) back the ordered map and set types in many standard libraries: Java's TreeMap, C++'s std::map, and similar structures elsewhere. They show up wherever we need fast lookups while maintaining sorted order. They are also an important topic for coding interviews, especially in problems that involve dynamic insertions, deletions, and ordered traversal.

In this chapter, I'll cover:

  • What a BST is and how it works
  • The core operations: search, insert, and delete
  • Different types of BSTs
  • How to implement a BST in code

What is a Binary Search Tree?

A Binary Search Tree is a binary tree with one extra rule, the BST property:

For every node:

  • All values in the left subtree are smaller than the node's value.
  • All values in the right subtree are greater than the node's value.

This property is what enables logarithmic operations: at each step, the search space halves, similar to how binary search works on a sorted array.

Consider inserting the values 50, 30, 70, 20, 40, 60, 80 into an empty tree. A balanced BST looks like this:

50302040706080
  • The left subtree of 50 contains values smaller than 50: {20, 30, 40}.
  • The right subtree of 50 contains values greater than 50: {60, 70, 80}.
  • The same property holds at every node in the tree.

To search for 60:

  • Start at 50; since 60 is greater, move right.
  • At 70; since 60 is smaller, move left.
  • Found 60.

Each comparison eliminates half of the remaining nodes, instead of scanning every node like in a linked list.

  • A balanced BST keeps its height close to log(n), so operations are typically O(log n)
  • Examples of balanced BSTs include AVL Trees, and Red-Black Trees.
  • An unbalanced BST can degrade to a linked list if nodes are inserted in sorted order making operations O(n) in the worst case

Key Operations in BSTs

BSTs support four core operations: search, insert, delete, and traversal. The examples below use this balanced BST:

50302040706080

All code examples will be methods within this basic BST class structure:

Searching in a BST works like binary search on a sorted array.

Here's the algorithm:

  1. Base Case 1 (Not Found): If the current root is null, we've hit a dead end. The target is not in the tree, so return false.
  2. Base Case 2 (Found): If the current root.val is equal to the target, we've found it! Return true.
  3. Recursive Step (Go Left): If the target is less than the root.val, it must be in the left subtree. Return the result of calling search on the root.left.
  4. Recursive Step (Go Right): Otherwise (if target is greater than root.val), it must be in the right subtree. Return the result of calling search on the root.right.

Example: Let's say you are searching for 60:

  • Start at 50. Since 60 is larger → go right.
  • At 70, since 60 is smaller → go left.
  • Found 60. Search is complete.

Average time complexity for search is O(log n) when the tree is balanced since each comparison eliminates roughly half of the remaining nodes.

But in the worst case it is O(n), if the tree is unbalanced (or skewed). For example, if you insert numbers in sorted order (1, 2, 3, 4, 5), it degenerates into a linked list.

Searching for 5 would require visiting every single node.

2. Insertion

Insertion works almost the same way as search.

We "search" for the value, and when we hit a null spot, we know that's where the new node belongs.

Here's what it looks like in code:

  1. If the current node (root) is null, we've found the empty spot. Create a new Node(val) and return it. This returned node will be assigned as the child of the parent node (from the previous recursive call).
  2. If val < root.val, recursively call insert on the left subtree. Set the current node's left child to be the result of this recursive call (this handles the linking).
  3. If val > root.val, recursively call insert on the right subtree. Set the current node's right child to be the result of this recursive call.
  4. Otherwise, the value already exists, so we return the current root unchanged. This passes the node's reference back up the call stack, keeping all links intact.

Example:

Insert 25 into the earlier tree.

  • Start at 50 → go left to 30 → go left again to 20.
  • At 20 go right (to null).
  • The call insert(null, 25) hits the base case. It creates Node(25) and returns it.
  • This returned node is assigned as the right child of 20.
5030202540706080

The complexity is identical to Search:

  • Average case: O(log n)
  • Worst case: O(n)

3. Deletion

Deletion is the most complex operation because we must remove a node while ensuring the BST property (left < parent < right) is maintained for the entire tree.

There are three distinct cases to handle.

Case 1: The Node is a Leaf (0 Children)

This is the simplest case. Remove the node by setting its parent's pointer to null.

Example: To delete 20, set 30.left = null.

Case 2: The Node has One Child

This is also simple. We "bypass" the node by linking its parent directly to its only child.

Example: if 60 had a child 65, we'd delete 60 by setting 70.left = 65.

Case 3: The Node has Two Children

This case is harder. Removing the node directly would leave two orphan subtrees.

The solution is to:

  1. Find a replacement node from one of its subtrees. The standard choice is the inorder successor (the smallest value in the node's right subtree).
  2. Copy the successor's value into the node we want to delete.
  3. Now, delete the original successor node from the right subtree. This deletion is guaranteed to be a simple Case 1 or Case 2, because the successor (smallest node) cannot have a left child.

Here's what the delete code looks like:

  1. If root is null, the value isn't here to delete. Return null.
  2. If val < root.val, the node to delete is in the left subtree. Recursively call delete on root.left and assign the result back to root.left.
  3. If val > root.val, the node is in the right subtree. Recursively call delete on root.right and assign the result back to root.right.
  4. Otherwise, we've found the node (root.val == val). Now we handle the three cases:
    • If root.left is null, we bypass the current node by returning root.right. (This covers a leaf node, where root.right is also null, and a node with one right child.)
    • Else, if root.right is null, we bypass the current node by returning root.left.
    • Case 3 (2 children):

a. Find the inorder successor (the smallest node in the right subtree) using the findMin(root.right) helper.

b. Copy the successor.val into the current node (root.val = successor.val).

c. Recursively call delete on the right subtree to remove the original successor node (passing successor.val). Assign the result back to root.right.

  1. Return the root (which may be unchanged, may have a new value, or may be replaced by a child) up the call stack.

Example: Delete 50

  1. delete(root, 50) is called. The else block (Step 4) is hit.
  2. root.left (30) and root.right (70) are not null. This is Case 3.
  3. findMin(root.right) is called on node 70. It goes left and finds 60.
  4. successor is node 60.
  5. root.val = successor.val; (The root node, formerly holding 50, now holds 60. The root node object is unchanged; only its value is overwritten.)
  6. delete(root.right, 60) is called to remove the original 60.
  7. This recursive call finds 60. 60.left is null, so it hits Case 1/2 and returns 60.right (which is null).
  8. 70.left is set to null.
  9. The same root node is returned, now holding the value 60 instead of 50.

The time complexity of delete is O(log n) on average if the tree is balanced, and O(n) in the worst case for a skewed tree.

Built-in Libraries

You rarely write a BST from scratch in practice. Most languages ship a sorted map and sorted set as part of their standard library, and these are the right starting point whenever a problem needs ordered keys, range queries, or O(log n) predecessor/successor lookups.

An important point: every production "BST" in standard libraries is a self-balancing variant. The standard implementations use:

  • Red-black trees: Java's TreeMap, C++'s std::map, C#'s SortedDictionary.
  • B-trees: Rust's BTreeMap, designed for cache locality at the cost of slightly more complex code.
  • A plain unbalanced BST is never used as a built-in container because adversarial insertion orders would degrade it to O(n).

The API stays the same in either case: insert, lookup, delete, and ordered traversal in O(log n).

TreeMap<K, V> and TreeSet<E> (in java.util) are red-black tree implementations. Keys are kept in sorted order, and the API exposes navigation methods like floorKey, ceilingKey, higherKey, and lowerKey for predecessor/successor queries.

For interview problems where the input fits in memory and the language has a built-in sorted map, use it. The implementation work is only meaningful when the problem explicitly asks you to write a balanced BST or when you need a structure the standard library doesn't offer (a treap with random rotations, an order-statistic tree, etc.).

This unbalanced worst case is exactly the problem that self-balancing BSTs (AVL trees, red-black trees) solve.

Quiz

Introduction Quiz

10 quizzes