# Binary Search Trees: Complete Interview Playbook

## 1\. What is a BST?

A Binary Search Tree is a binary tree where every node obeys a single invariant:

> For any node N, all values in its **left subtree** are strictly less than N, and all values in its **right subtree** are strictly greater than N. This holds recursively at every node.

```plaintext
        8
       / \
      3   10
     / \    \
    1   6    14
       / \   /
      4   7 13
```

This ordering lets you binary-search the tree just like a sorted array. Each comparison eliminates half the remaining candidates — giving O(log n) expected performance for all core operations.

**The single most useful property:** Inorder traversal (left → root → right) of a BST always produces values in <mark class="bg-yellow-200 dark:bg-yellow-500/30">sorted ascending order</mark>. You will exploit this in Kth Smallest, Inorder Successor, and validation problems.

### Node structure

```python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val   = val
        self.left  = left
        self.right = right
```

* * *

## 2\. Insert

### Intuition

Inserting a value is a guided descent from the root. At each node, the BST property tells you exactly which direction to go. When you fall off the tree (hit `None`), you've found the right spot

### Recursive implementation

```python
def insert(root, val):
    if not root:
        return TreeNode(val)          # found the empty slot
    if val < root.val:
        root.left  = insert(root.left,  val)
    elif val > root.val:
        root.right = insert(root.right, val)
    # val == root.val → duplicate; ignore (standard BST convention)
    return root
```

The key insight: every recursive call returns the (possibly new) root of that subtree. The parent wires up `root.left = ...` or `root.right = ...` with whatever comes back. This is a clean way to handle node creation without special-casing the parent pointer.

### Iterative implementation

```python
def insert_iter(root, val):
    node = TreeNode(val)
    if not root:
        return node
    cur = root
    while True:
        if val < cur.val:
            if cur.left is None:
                cur.left = node
                break
            cur = cur.left
        else:
            if cur.right is None:
                cur.right = node
                break
            cur = cur.right
    return root
```

The iterative version uses O(1) extra space instead of O(h) call-stack space. In skewed trees with n = 10⁵ nodes, recursion can overflow the stack — prefer iterative in interviews unless you explicitly discuss it.

### Step-by-step trace — inserting 5 into the example tree

```plaintext
Start at root = 8  → 5 < 8  → go left
At node 3          → 5 > 3  → go right
At node 6          → 5 < 6  → go left
At node 4          → 5 > 4  → go right
At node None       → place 5 here ✓
```

### Complexity

| Case | Time | Space (recursive) |
| --- | --- | --- |
| Balanced tree | O(log n) | O(log n) |
| Skewed tree (worst) | O(n) | O(n) |

Solve problem - [Insert Into a Binary Search Tree](https://leetcode.com/problems/insert-into-a-binary-search-tree/description/)

* * *

## 3\. Search

### Intuition

Identical motion to insert — follow the BST property downward. You stop when you either find the value or fall off the tree.

### Recursive

```python
def search(root, target):
    if not root or root.val == target:
        return root             # None → not found; node → found
    if target < root.val:
        return search(root.left,  target)
    return search(root.right, target)
```

### Iterative (preferred in interviews)

```python
def search_iter(root, target):
    while root and root.val != target:
        root = root.left if target < root.val else root.right
    return root
```

This is naturally tail-recursive, so the iterative form is direct. It avoids any stack overhead and is what you should default to.

### Complexity

Same as insert: O(log n) balanced, O(n) worst case on a skewed tree.

Solve problem - [Search in a Binary Tree](https://leetcode.com/problems/search-in-a-binary-search-tree/description/)

* * *

## 4\. Delete

Delete is the hardest BST operation. Three structural cases arise based on how many children the target node has.

### Case 1 — Leaf node (no children)

Simply return `None` to the parent. The node vanishes.

```plaintext
Delete 7 from the example tree:
    6            6
   / \    →     /
  4   7         4
```

### Case 2 — One child

Bypass the node entirely. Return its only child up to the parent.

```plaintext
Delete 10 (has only right child 14):
    8             8
   / \    →      / \
  3   10        3   14
        \           /
        14          13
```

### Case 3 — Two children (the tricky one)

You cannot simply remove the node because it holds structure together. The standard approach:

1.  Find the **inorder successor**: the smallest value in the right subtree (go right once, then leftmost).
    
2.  Copy that successor's value into the current node.
    
3.  Delete the successor from the right subtree (it will have at most one child — a right child — since it's the leftmost node).
    

Why the inorder successor? Because it is the smallest value greater than the current node. Placing it here preserves the BST invariant: it's still greater than everything in the left subtree, and smaller than everything else in the right subtree.

### Full implementation

```python
def delete(root, key):
    if not root:
        return None

    if key < root.val:
        root.left  = delete(root.left,  key)
    elif key > root.val:
        root.right = delete(root.right, key)
    else:
        # Found the node to delete
        if not root.left:           # Case 1 or Case 2 (no left child)
            return root.right
        if not root.right:          # Case 2 (no right child)
            return root.left

        # Case 3: two children
        # Find inorder successor (min of right subtree)
        successor = root.right
        while successor.left:
            successor = successor.left

        root.val   = successor.val                      # copy value up
        root.right = delete(root.right, successor.val)  # delete successor

    return root

def find_min(node):
    while node.left:
        node = node.left
    return node
```

### Step-by-step trace — deleting 3 from the example tree

```plaintext
Target: 3  (two children: 1 and 6)

Inorder successor of 3 = min of right subtree of 3
  → go right to 6, then leftmost → 4
  
Copy 4 into node (was 3):
        8
       / \
      4   10    ← node now holds 4
     / \    \
    1   6    14
       / \   /
      4   7 13  ← this 4 still needs to be deleted

Delete 4 from right subtree of node-now-4:
  4 has no left child → return its right child (None)

Final:
        8
       / \
      4   10
     / \    \
    1   6    14
         \   /
          7 13
```

### Complexity

| Case | Time |
| --- | --- |
| Balanced | O(log n) |
| Skewed (worst) | O(n) |

Solve problem - Delete Node in a B[Delete Node in a BST](https://leetcode.com/problems/delete-node-in-a-bst/description/)

* * *

## 5\. O(log n) vs O(n) — Why Worst Case is Linear

This is one of the most common follow-up questions in interviews. You must be able to explain it clearly.

### Why O(log n)?

In a perfectly balanced BST with n nodes, the height h = log₂(n). Every operation (insert, search, delete) does at most one comparison per level, so it visits at most h nodes → O(log n) (height of tree)

### Why O(n)?

The BST property says nothing about balance. If you insert already-sorted data, every new node goes to the right of the previous one:

```plaintext
Insert: 1, 2, 3, 4, 5

1
 \
  2
   \
    3
     \
      4
       \
        5
```

This is a valid BST — the invariant holds — but it's structurally a linked list. Height = n. Searching for 5 visits all 5 nodes → O(n).

### The core tradeoff

| Tree shape | Height | Operation time |
| --- | --- | --- |
| Perfect balance | log n | O(log n) |
| Random inserts (average) | ~1.39 log n | O(log n) |
| Sorted inserts (worst) | n | O(n) |
| Reverse-sorted inserts (worst) | n | O(n) |

### How do self-balancing BSTs fix this?

AVL trees and Red-Black trees add rotation rules that maintain height ≤ O(log n) after every insert and delete. Python's `SortedList` (from `sortedcontainers`) and Java's `TreeMap` are backed by these structures. For interviews, you don't implement them from scratch — but knowing they exist and why is expected.

### What to say in an interview

BST gives O(log n) average case assuming the tree is reasonably balanced. In the worst case — when input is sorted or reverse-sorted — the tree degenerates into a linked list and all operations become O(n). This is why production systems use self-balancing variants like AVL or Red-Black trees.

* * *

## 6\. Validate BST

**LeetCode 98 —** [**Validate Binary Search Tree (Medium)**](https://leetcode.com/problems/validate-binary-search-tree/description/)

### The naive mistake

A common wrong approach: check that `node.left.val < node.val < node.right.val` at every node. This fails on cases like:

```plaintext
    5
   / \
  1   4
     / \
    3   6
```

At node 4: `3 < 4 < 6` ✓ locally. But 3 and 4 are in the right subtree of 5, so they must all be > 5. This tree is **invalid** and the local check misses it.

### Correct approach: pass valid range down

Every node must satisfy `min_val < node.val < max_val`. As you recurse, tighten the bounds:

*   Going left: the current node's value becomes the new upper bound.
    
*   Going right: the current node's value becomes the new lower bound.
    

```python
def isValidBST(root):
    def validate(node, min_val, max_val):
        if not node:
            return True
        if not (min_val < node.val < max_val):
            return False
        return (validate(node.left,  min_val,   node.val) and
                validate(node.right, node.val,  max_val))

    return validate(root, float('-inf'), float('inf'))
```

### Trace through the invalid example above

```plaintext
validate(5,  -inf,  +inf) → -inf < 5 < +inf ✓
  validate(1,  -inf,  5)  → -inf < 1 < 5    ✓
  validate(4,   5,  +inf) → 5 < 4 < +inf    ✗ → return False
```

Returns False correctly.

### Alternative: inorder traversal must be strictly increasing

```python
def isValidBST_inorder(root):
    prev = [float('-inf')]   # use list for mutability in closure

    def inorder(node):
        if not node:
            return True
        if not inorder(node.left):
            return False
        if node.val <= prev[0]:
            return False
        prev[0] = node.val
        return inorder(node.right)

    return inorder(root)
```

This works because inorder traversal of a valid BST must produce a strictly increasing sequence. If any value is ≤ the previous, the BST property is violated.

Both approaches are O(n) time, O(h) space. The bounds-passing approach is slightly more intuitive to explain; the inorder approach leverages the sorted-inorder property directly.

* * *

## 7\. Kth Smallest Element in a BST

**LeetCode 230 —** [**Kth Smallest Element in a BST (Medium)**](https://leetcode.com/problems/kth-smallest-element-in-a-bst/description/)

### Key insight

Inorder traversal visits BST nodes in ascending order. The kth node visited is the kth smallest. No sorting needed — the BST structure gives it to you.

### Recursive approach

```python
def kthSmallest(root, k):
    result = [0]
    count  = [0]

    def inorder(node):
        if not node or count[0] == k:
            return
        inorder(node.left)
        count[0] += 1
        if count[0] == k:
            result[0] = node.val
            return
        inorder(node.right)

    inorder(root)
    return result[0]
```

### Iterative approach (preferred — avoids recursion limit)

```python
def kthSmallest_iter(root, k):
    stack = []
    cur   = root

    while cur or stack:
        while cur:              # go as far left as possible
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()       # visit
        k -= 1
        if k == 0:
            return cur.val
        cur = cur.right         # move to right subtree
```

### Trace on the example tree, k=3

```plaintext
Push: 8 → 3 → 1
Pop 1: k=3→2, cur=None
Pop 3: k=2→1, cur=6
Push: 6 → 4
Pop 4: k=1→0 → return 4  ✓

Sorted order: 1, 3, 4, 6, 7, 8, 10, 13, 14
3rd smallest = 4
```

### Complexity

O(h + k) time (h to reach the leftmost, then k pops), O(h) space for the stack.

**Follow-up question:** "What if inserts/deletes happen frequently and you need kth smallest after each operation?" The answer is to augment each node with a `left_count` field (size of left subtree). Then you can find kth in O(log n) without traversal.

* * *

## 8\. Convert Sorted Array to BST

**LeetCode 108 —** [**Convert Sorted Array to Binary Search Tree (Easy)**](https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/description/)

### Problem

Given a sorted array, construct a height-balanced BST. Height-balanced means the height difference between left and right subtrees of any node is at most 1.

### Insight

The middle element of the array should become the root. Everything to its left forms the left subtree; everything to its right forms the right subtree. Apply this recursively on each half.

This is the same principle as binary search: always pick the midpoint.

```python
def sortedArrayToBST(nums):
    def build(lo, hi):
        if lo > hi:
            return None
        mid  = (lo + hi) // 2
        node = TreeNode(nums[mid])
        node.left  = build(lo,      mid - 1)
        node.right = build(mid + 1, hi)
        return node

    return build(0, len(nums) - 1)
```

### Trace on \[1, 2, 3, 4, 5, 6, 7\]

```plaintext
build(0, 6) → mid=3 → root=4
  build(0, 2) → mid=1 → node=2
    build(0, 0) → mid=0 → node=1 (leaf)
    build(2, 2) → mid=2 → node=3 (leaf)
  build(4, 6) → mid=5 → node=6
    build(4, 4) → mid=4 → node=5 (leaf)
    build(6, 6) → mid=6 → node=7 (leaf)

Result:
        4
       / \
      2   6
     / \ / \
    1  3 5  7
```

Perfectly balanced: every level is filled. Height = log₂(7) ≈ 3.

### Complexity

O(n) time (each element visited once), O(log n) space (recursion depth = height of balanced tree).

**Variant:** LeetCode 109 — Convert Sorted List to BST. Same idea, but you can't index into a linked list. Use slow/fast pointers to find the midpoint, then recurse on each half. O(n log n) time unless you use inorder simulation.

* * *

## 9\. Inorder Successor and Predecessor

These are two of the most asked BST problems in onsite interviews. Understand them cold.

### Definitions

*   **Inorder successor** of node P: the node with the smallest value greater than P.val. In inorder traversal, it's the node that comes immediately after P.
    
*   **Inorder predecessor** of node P: the node with the largest value less than P.val. In inorder traversal, it's the node that comes immediately before P.
    

### Case analysis for Inorder Successor

**Case 1: P has a right subtree.** The successor is the leftmost node in P's right subtree (the minimum of the right subtree).

```plaintext
Successor of 3 in the example tree:
  3 has right subtree rooted at 6
  Leftmost of that subtree = 4
  → successor is 4
```

**Case 2: P has no right subtree.** Walk up the tree using parent pointers. The successor is the first ancestor for which P is in the left subtree (the first ancestor with a greater value).

```plaintext
Successor of 7 in the example tree:
  7 has no right child
  Go up: parent is 6 → 7 is in 6's right subtree → skip
  Go up: parent is 3 → 6 is in 3's right subtree → skip
  Go up: parent is 8 → 3 is in 8's left subtree → 8 is the ancestor ✓
  → successor is 8
```

### Implementation (with parent pointers)

```python
def inorder_successor(root, p):
    successor = None
    cur = root

    while cur:
        if p.val < cur.val:
            successor = cur         # cur is a candidate
            cur = cur.left          # try to find something smaller
        else:
            cur = cur.right         # p is >= cur, successor must be to the right

    return successor
```

This elegant solution doesn't need parent pointers. It uses the BST property: at each node, if `p.val < cur.val`, cur is a valid successor candidate (record it and go left to find a smaller one). If `p.val >= cur.val`, the successor must be in the right subtree.

### Case analysis for Inorder Predecessor

Mirror image of successor:

*   **P has a left subtree:** predecessor = rightmost node in left subtree (maximum of left subtree).
    
*   **P has no left subtree:** predecessor = first ancestor for which P is in the right subtree.
    

```python
def inorder_predecessor(root, p):
    predecessor = None
    cur = root

    while cur:
        if p.val > cur.val:
            predecessor = cur       # cur is a candidate
            cur = cur.right         # try to find something larger
        else:
            cur = cur.left

    return predecessor
```

### Full trace — successor of 6

```plaintext
cur=8:  6 < 8  → successor=8, go left
cur=3:  6 > 3  → go right
cur=6:  6 == 6 → go right
cur=7:  6 < 7  → successor=7, go left
cur=None → stop

Return 7 ✓
```

### Why this works without parent pointers

At every step, the BST property tells you: if `p.val < cur.val`, then cur is "to the right of" p in inorder, making it a valid successor. By always going left after recording a candidate, you find the smallest such ancestor — which is the true successor.

### LeetCode 285 variant (with access to root only)

LeetCode 285 — Inorder Successor in BST — gives you the root and the target node p. The solution above handles it directly. LeetCode 510 — Inorder Successor in BST II — gives you direct access to the node with a parent pointer, enabling the classic two-case approach.

Problem - [Inorder Successor in BST](https://leetcode.com/problems/inorder-successor-in-bst/description/)

* * *

## 10\. LeetCode Problem List

Work through these in the order listed. The first five are the core operations; the last five are pattern extensions.

| # | Problem | Difficulty | Key concept |
| --- | --- | --- | --- |
| 700 | [Search in a Binary Search Tree](https://leetcode.com/problems/search-in-a-binary-search-tree/description/) | Easy | Pure BST search |
| 701 | [Insert into a Binary Search Tree](https://leetcode.com/problems/insert-into-a-binary-search-tree/description/) | Medium | Recursive insert |
| 450 | [Delete Node in a BST](https://leetcode.com/problems/delete-node-in-a-bst/description/) | Medium | 3-case delete |
| 98 | [Validate Binary Search Tree](https://leetcode.com/problems/validate-binary-search-tree/) | Medium | Range bounds, inorder |
| 230 | [Kth Smallest Element in a BST](https://leetcode.com/problems/kth-smallest-element-in-a-bst/description/) | Medium | Inorder traversal |
| 108 | [Convert Sorted Array to Binary Search Tree](https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/description/) | Easy | Divide and conquer |
| 109 | [Convert Sorted List to Binary Search Tree](https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/description/) | Medium | Slow/fast pointer + 108 |
| 285 | [Inorder Successor in BST](https://leetcode.com/problems/inorder-successor-in-bst/description/) | Medium | BST property descent |
| 510 | [Inorder Successor in BST II](https://leetcode.com/problems/inorder-successor-in-bst-ii/description/) | Medium | Parent pointer + 285 |
| 173 | [Binary Search Tree Iterator](https://leetcode.com/problems/binary-search-tree-iterator/description/) | Medium | Iterative inorder |

### Bonus (once you're comfortable)

| # | Problem | Difficulty | Key concept |
| --- | --- | --- | --- |
| 653 | [Two Sum IV — Input is a BST](https://leetcode.com/problems/two-sum-iv-input-is-a-bst/description/) | Easy | Inorder + two-pointer |
| 669 | [Trim a Binary Search Tree](https://leetcode.com/problems/trim-a-binary-search-tree/description/) | Medium | Recursive trim with bounds |
| 1038 | [BST to Greater Sum Tree](https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/description/) | Medium | Reverse inorder (right → root → left) |
| 99 | [Recover Binary Search Tree](https://leetcode.com/problems/recover-binary-search-tree/description/) | Hard | Two swapped nodes in inorder |

* * *

## Quick Reference Card

*   INSERT → recurse left/right; place at first None; O(log n) avg, O(n) worst
    
*   SEARCH → recurse left/right; return node or None; O(log n) avg, O(n) worst
    
*   DELETE → 3 cases: leaf / one child / two children (use inorder successor)
    
*   VALIDATE → pass (min, max) bounds; tighten at each level; O(n)
    
*   KTH → iterative inorder; pop kth node; O(h + k)
    
*   BUILD → always pick midpoint as root; recurse on halves; O(n)
    
*   SUCCESSOR → has right child? → min(right subtree); else → first ancestor where you came from left
    
*   PREDECESSOR → has left child? → max(left subtree); else → first ancestor where you came from right
    
*   WORST CASE O(n): sorted/reverse-sorted input → skewed tree → height = n FIX: AVL tree, Red-Black tree, treap (all guarantee O(log n) worst case)