# Binary Search Tree Operations — Search, Insert, Delete, Validate and K-th Smallest

Source: https://skills101.in/learn/dsa/dsa-binary-search-tree-operations — Skills101 free tutorial (Data Structures & Algorithms). Updated 2026-11-18.

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.

![A BST built from 50 30 70 20 40 60 80 65; searching for 65 visits only 50, 70, 60 and 65, highlighted along one path from the root](https://skills101.in/learn-img/dsa/bst-search.svg)

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

```python
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))
```

```text
[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:

1. **Leaf** (no children): just remove it.
2. **One child**: replace the node with its child.
3. **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.

![Deleting 50, which has two children: its inorder successor 60 (the smallest key in the right subtree) is copied up to the root, and 65 takes 60's old place](https://skills101.in/learn-img/dsa/bst-delete.svg)

```python
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))
```

```text
[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.

```python
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))
```

```text
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:

```java
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));
    }
}
```

```text
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 `insert` and `delete`, 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.


Practice quiz and free certificate: https://skills101.in/learn/dsa/dsa-binary-search-tree-operations