AdvancedData Structures & Algorithms · Lesson 26 of 29 · Updated ·
Binary Search Tree Operations — Search, Insert, Delete, Validate and K-th Smallest
A binary search tree (BST) is a binary tree with one rule: for every node, all keys in its left subtree are smaller than the node's key, and all keys in its right subtree are larger. That one rule lets us find a key the way you find a word in a dictionary — by throwing away half of what is left at each step. This lesson builds the operations that interviews ask for most.
1. The BST rule and why it helps
Take the keys 50, 30, 70, 20, 40, 60, 80, 65 and insert them one by one. Each new key walks down from the root: smaller goes left, larger goes right, until it finds an empty spot.
To search for 65, we compare with 50 (go right), then 70 (go left), then 60 (go right) and find it. We never look at 20, 30, 40 or 80.
The cost of search, insert and delete is O(h), where h is the height of the tree (the number of edges on the longest root-to-leaf path).
| Shape of the tree | Height h | Search cost |
|---|---|---|
| balanced (like the picture) | about log₂ n | O(log n) |
| keys inserted in sorted order (1, 2, 3, …) | n − 1, a "linked list" | O(n) |
That second row matters: a plain BST gives no guarantee. Self-balancing trees (AVL, red-black) keep the height near log n. Java's TreeMap and C++'s std::map are red-black trees, so they guarantee O(log n).
2. Search and insert
class Node:
def __init__(self, key):
self.key, self.left, self.right = key, None, None
def insert(root, key):
if root is None:
return Node(key)
if key < root.key:
root.left = insert(root.left, key)
elif key > root.key:
root.right = insert(root.right, key)
return root # equal key: ignore the duplicate
def search(root, key):
while root and root.key != key:
root = root.left if key < root.key else root.right
return root is not None
def inorder(root, out):
if root:
inorder(root.left, out); out.append(root.key); inorder(root.right, out)
return out
root = None
for k in [50, 30, 70, 20, 40, 60, 80, 65]:
root = insert(root, k)
print(inorder(root, []))
print(search(root, 65), search(root, 55))
[20, 30, 40, 50, 60, 65, 70, 80]
True False
Notice the inorder traversal (left, root, right) prints the keys in sorted order. This is the most useful fact about BSTs: many BST problems are really "do an inorder traversal and use the sorted order".
3. Delete: three cases
Deleting is the only tricky operation. First find the node, then:
- Leaf (no children): just remove it.
- One child: replace the node with its child.
- Two children: find the inorder successor — the smallest key in the right subtree (go right once, then left as far as possible). Copy its key into the node, then delete the successor from the right subtree. The successor has no left child, so that second delete is case 1 or 2.
class Node:
def __init__(self, key):
self.key, self.left, self.right = key, None, None
def insert(root, key):
if root is None:
return Node(key)
if key < root.key:
root.left = insert(root.left, key)
elif key > root.key:
root.right = insert(root.right, key)
return root
def delete(root, key):
if root is None:
return None
if key < root.key:
root.left = delete(root.left, key)
elif key > root.key:
root.right = delete(root.right, key)
else:
if root.left is None: # cases 1 and 2
return root.right
if root.right is None:
return root.left
succ = root.right # case 3
while succ.left:
succ = succ.left
root.key = succ.key
root.right = delete(root.right, succ.key)
return root
def preorder(r):
return [r.key] + preorder(r.left) + preorder(r.right) if r else []
root = None
for k in [50, 30, 70, 20, 40, 60, 80, 65]:
root = insert(root, k)
root = delete(root, 20) # leaf
root = delete(root, 60) # one child (65)
root = delete(root, 50) # two children
print(preorder(root))
[65, 30, 40, 70, 80]
Using the inorder predecessor (the largest key in the left subtree) works just as well.
4. Validate a BST
A common wrong answer only checks each node against its two children. That misses cases like this: root 10, left child 5, and 5's right child 12. Each parent–child pair looks fine, but 12 sits in 10's left subtree, so the tree is not a BST.
The right way passes down an allowed range (low, high). Going left lowers the upper limit to the current key; going right raises the lower limit.
class Node:
def __init__(self, key, left=None, right=None):
self.key, self.left, self.right = key, left, right
def is_bst(node, low=float('-inf'), high=float('inf')):
if node is None:
return True
if not (low < node.key < high):
return False
return is_bst(node.left, low, node.key) and is_bst(node.right, node.key, high)
good = Node(10, Node(5, Node(2), Node(7)), Node(15))
bad = Node(10, Node(5, Node(2), Node(12)), Node(15))
print(is_bst(good), is_bst(bad))
True False
Another correct method: do an inorder traversal and check that every key is strictly bigger than the previous one.
5. K-th smallest key
Because inorder visits keys in sorted order, the k-th key it visits is the k-th smallest. Stop as soon as you reach it. Here is the iterative version in Java, using an explicit stack:
import java.util.*;
public class Main {
static class Node {
int key; Node left, right;
Node(int k) { key = k; }
}
static Node insert(Node root, int key) {
if (root == null) return new Node(key);
if (key < root.key) root.left = insert(root.left, key);
else if (key > root.key) root.right = insert(root.right, key);
return root;
}
static int kthSmallest(Node root, int k) {
Deque<Node> stack = new ArrayDeque<>();
Node cur = root;
while (cur != null || !stack.isEmpty()) {
while (cur != null) { stack.push(cur); cur = cur.left; }
cur = stack.pop();
if (--k == 0) return cur.key;
cur = cur.right;
}
return -1; // k is larger than the number of keys
}
public static void main(String[] args) {
Node root = null;
for (int k : new int[]{50, 30, 70, 20, 40, 60, 80, 65}) root = insert(root, k);
System.out.println(kthSmallest(root, 1) + " " + kthSmallest(root, 3) + " " + kthSmallest(root, 6));
}
}
20 40 65
This costs O(h + k): we walk down to the smallest key, then take k steps.
Common mistakes
- Validating a BST by comparing each node only with its direct children. Use a (low, high) range or the inorder check.
- Forgetting to return the (possibly new) root from
insertanddelete, so the change is lost. - In delete with two children, deleting the successor from the whole tree instead of from the right subtree.
- Assuming BST operations are always O(log n). A plain BST built from sorted input has height n − 1.
- Not deciding how to handle duplicate keys. Pick a rule (ignore, count, or always go right) and follow it everywhere.
Quick recap
- BST rule: left subtree keys < node key < right subtree keys.
- Search, insert and delete cost O(h): O(log n) when balanced, O(n) in the worst case.
- Inorder traversal of a BST gives the keys in sorted order.
- Delete with two children: copy in the inorder successor, then delete the successor.
- Validate with a (low, high) range; the k-th smallest is the k-th key of an inorder walk.