# Binary Search Trees — Part 2: Interview Problems

Six problems that exploit the BST invariant: one-path walks, range validation, inorder order statistics and balanced construction.

## 1. Search in a Binary Search Tree (LeetCode 700)

**🟢 Easy.** Return the subtree rooted at the node with value `val`, or null.

```text
root = [4,2,7,1,3], val = 2 → [2,1,3]
```

**Approach.** Walk down: go left if `val` is smaller than the current node, right if larger.

**Complexity.** O(h) time, O(1) space iteratively.

```typescript
class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}
function _tree(level: (number | null)[]): TreeNode | null {
  if (!level.length || level[0] === null) return null;
  const root = new TreeNode(level[0]); const q: TreeNode[] = [root]; let i = 1;
  while (q.length && i < level.length) {
    const node = q.shift()!;
    if (i < level.length && level[i] !== null) { node.left = new TreeNode(level[i]!); q.push(node.left); }
    i++;
    if (i < level.length && level[i] !== null) { node.right = new TreeNode(level[i]!); q.push(node.right); }
    i++;
  }
  return root;
}
function _level(root: TreeNode | null): (number | null)[] {
  const out: (number | null)[] = []; const q: (TreeNode | null)[] = [root];
  while (q.length) { const n = q.shift()!; if (n) { out.push(n.val); q.push(n.left, n.right); } else out.push(null); }
  while (out.length && out[out.length - 1] === null) out.pop();
  return out;
}

function searchBST(root: TreeNode | null, val: number): TreeNode | null {
  while (root && root.val !== val) root = val < root.val ? root.left : root.right;
  return root;
}
```

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

def _tree(level):
    if not level or level[0] is None:
        return None
    root = TreeNode(level[0]); q = [root]; i = 1
    while q and i < len(level):
        node = q.pop(0)
        if i < len(level) and level[i] is not None:
            node.left = TreeNode(level[i]); q.append(node.left)
        i += 1
        if i < len(level) and level[i] is not None:
            node.right = TreeNode(level[i]); q.append(node.right)
        i += 1
    return root

def _level(root):
    out, q = [], [root]
    while q:
        n = q.pop(0)
        if n:
            out.append(n.val); q.append(n.left); q.append(n.right)
        else:
            out.append(None)
    while out and out[-1] is None:
        out.pop()
    return out

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

## 2. Validate Binary Search Tree (LeetCode 98)

**🟠 Medium.** Return `true` if the tree is a valid BST (strictly smaller on the left, strictly larger on the right, for every ancestor).

```text
[5,4,6,null,null,3,7] → false   (3 is in 5's right subtree but smaller than 5)
```

**Approach.** Pass the allowed open interval `(low, high)` down the tree. The left child inherits `(low, node.val)`, the right child `(node.val, high)`.

**Complexity.** O(n) time, O(h) stack.

```typescript
class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}
function _tree(level: (number | null)[]): TreeNode | null {
  if (!level.length || level[0] === null) return null;
  const root = new TreeNode(level[0]); const q: TreeNode[] = [root]; let i = 1;
  while (q.length && i < level.length) {
    const node = q.shift()!;
    if (i < level.length && level[i] !== null) { node.left = new TreeNode(level[i]!); q.push(node.left); }
    i++;
    if (i < level.length && level[i] !== null) { node.right = new TreeNode(level[i]!); q.push(node.right); }
    i++;
  }
  return root;
}
function _level(root: TreeNode | null): (number | null)[] {
  const out: (number | null)[] = []; const q: (TreeNode | null)[] = [root];
  while (q.length) { const n = q.shift()!; if (n) { out.push(n.val); q.push(n.left, n.right); } else out.push(null); }
  while (out.length && out[out.length - 1] === null) out.pop();
  return out;
}

function isValidBST(root: TreeNode | null): boolean {
  const ok = (node: TreeNode | null, low: number, high: number): boolean => {
    if (!node) return true;
    if (!(low < node.val && node.val < high)) return false;
    return ok(node.left, low, node.val) && ok(node.right, node.val, high);
  };
  return ok(root, -Infinity, Infinity);
}
```

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

def _tree(level):
    if not level or level[0] is None:
        return None
    root = TreeNode(level[0]); q = [root]; i = 1
    while q and i < len(level):
        node = q.pop(0)
        if i < len(level) and level[i] is not None:
            node.left = TreeNode(level[i]); q.append(node.left)
        i += 1
        if i < len(level) and level[i] is not None:
            node.right = TreeNode(level[i]); q.append(node.right)
        i += 1
    return root

def _level(root):
    out, q = [], [root]
    while q:
        n = q.pop(0)
        if n:
            out.append(n.val); q.append(n.left); q.append(n.right)
        else:
            out.append(None)
    while out and out[-1] is None:
        out.pop()
    return out

def is_valid_bst(root):
    def ok(node, low, high):
        if not node:
            return True
        if not (low < node.val < high):
            return False
        return ok(node.left, low, node.val) and ok(node.right, node.val, high)
    return ok(root, float("-inf"), float("inf"))
```

## 3. Kth Smallest Element in a BST (LeetCode 230)

**🟠 Medium.** Return the k-th smallest value (1-indexed) in a BST.

```text
[5,3,6,2,4,null,null,1], k = 3 → 3
```

**Approach.** Iterative inorder traversal visits values in sorted order; stop at the k-th visit. Follow-up: if the tree changes often and k-th queries are frequent, store subtree sizes in each node for O(h) queries.

**Complexity.** O(h + k) time, O(h) space.

```typescript
class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}
function _tree(level: (number | null)[]): TreeNode | null {
  if (!level.length || level[0] === null) return null;
  const root = new TreeNode(level[0]); const q: TreeNode[] = [root]; let i = 1;
  while (q.length && i < level.length) {
    const node = q.shift()!;
    if (i < level.length && level[i] !== null) { node.left = new TreeNode(level[i]!); q.push(node.left); }
    i++;
    if (i < level.length && level[i] !== null) { node.right = new TreeNode(level[i]!); q.push(node.right); }
    i++;
  }
  return root;
}
function _level(root: TreeNode | null): (number | null)[] {
  const out: (number | null)[] = []; const q: (TreeNode | null)[] = [root];
  while (q.length) { const n = q.shift()!; if (n) { out.push(n.val); q.push(n.left, n.right); } else out.push(null); }
  while (out.length && out[out.length - 1] === null) out.pop();
  return out;
}

function kthSmallest(root: TreeNode | null, k: number): number {
  const stack: TreeNode[] = [];
  let node = root;
  while (true) {
    while (node) { stack.push(node); node = node.left; }
    node = stack.pop()!;
    if (--k === 0) return node.val;
    node = node.right;
  }
}
```

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

def _tree(level):
    if not level or level[0] is None:
        return None
    root = TreeNode(level[0]); q = [root]; i = 1
    while q and i < len(level):
        node = q.pop(0)
        if i < len(level) and level[i] is not None:
            node.left = TreeNode(level[i]); q.append(node.left)
        i += 1
        if i < len(level) and level[i] is not None:
            node.right = TreeNode(level[i]); q.append(node.right)
        i += 1
    return root

def _level(root):
    out, q = [], [root]
    while q:
        n = q.pop(0)
        if n:
            out.append(n.val); q.append(n.left); q.append(n.right)
        else:
            out.append(None)
    while out and out[-1] is None:
        out.pop()
    return out

def kth_smallest(root, k):
    stack, node = [], root
    while True:
        while node:
            stack.append(node); node = node.left
        node = stack.pop()
        k -= 1
        if k == 0:
            return node.val
        node = node.right
```

## 4. Lowest Common Ancestor of a BST (LeetCode 235)

**🟠 Medium.** Return the lowest common ancestor of nodes `p` and `q` in a BST.

```text
[6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 → 6
```

**Approach.** Use the ordering: if both values are smaller than the node, the LCA is in the left subtree; if both are larger, in the right; otherwise the node splits them and is the LCA.

**Complexity.** O(h) time, O(1) space.

```typescript
class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}
function _tree(level: (number | null)[]): TreeNode | null {
  if (!level.length || level[0] === null) return null;
  const root = new TreeNode(level[0]); const q: TreeNode[] = [root]; let i = 1;
  while (q.length && i < level.length) {
    const node = q.shift()!;
    if (i < level.length && level[i] !== null) { node.left = new TreeNode(level[i]!); q.push(node.left); }
    i++;
    if (i < level.length && level[i] !== null) { node.right = new TreeNode(level[i]!); q.push(node.right); }
    i++;
  }
  return root;
}
function _level(root: TreeNode | null): (number | null)[] {
  const out: (number | null)[] = []; const q: (TreeNode | null)[] = [root];
  while (q.length) { const n = q.shift()!; if (n) { out.push(n.val); q.push(n.left, n.right); } else out.push(null); }
  while (out.length && out[out.length - 1] === null) out.pop();
  return out;
}

function lcaBst(root: TreeNode | null, p: number, q: number): number {
  let node = root;
  while (node) {
    if (p < node.val && q < node.val) node = node.left;
    else if (p > node.val && q > node.val) node = node.right;
    else return node.val;
  }
  return -1;
}
```

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

def _tree(level):
    if not level or level[0] is None:
        return None
    root = TreeNode(level[0]); q = [root]; i = 1
    while q and i < len(level):
        node = q.pop(0)
        if i < len(level) and level[i] is not None:
            node.left = TreeNode(level[i]); q.append(node.left)
        i += 1
        if i < len(level) and level[i] is not None:
            node.right = TreeNode(level[i]); q.append(node.right)
        i += 1
    return root

def _level(root):
    out, q = [], [root]
    while q:
        n = q.pop(0)
        if n:
            out.append(n.val); q.append(n.left); q.append(n.right)
        else:
            out.append(None)
    while out and out[-1] is None:
        out.pop()
    return out

def lca_bst(root, p, q):
    node = root
    while node:
        if p < node.val and q < node.val:
            node = node.left
        elif p > node.val and q > node.val:
            node = node.right
        else:
            return node.val
```

## 5. Insert into a Binary Search Tree (LeetCode 701)

**🟠 Medium.** Insert `val` (not already present) into the BST and return the root.

```text
[4,2,7,1,3], val = 5 → [4,2,7,1,3,5]
```

**Approach.** Walk down as in search until you fall off the tree; attach the new node there. The recursive version returns the (possibly new) subtree root.

**Complexity.** O(h) time.

```typescript
class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}
function _tree(level: (number | null)[]): TreeNode | null {
  if (!level.length || level[0] === null) return null;
  const root = new TreeNode(level[0]); const q: TreeNode[] = [root]; let i = 1;
  while (q.length && i < level.length) {
    const node = q.shift()!;
    if (i < level.length && level[i] !== null) { node.left = new TreeNode(level[i]!); q.push(node.left); }
    i++;
    if (i < level.length && level[i] !== null) { node.right = new TreeNode(level[i]!); q.push(node.right); }
    i++;
  }
  return root;
}
function _level(root: TreeNode | null): (number | null)[] {
  const out: (number | null)[] = []; const q: (TreeNode | null)[] = [root];
  while (q.length) { const n = q.shift()!; if (n) { out.push(n.val); q.push(n.left, n.right); } else out.push(null); }
  while (out.length && out[out.length - 1] === null) out.pop();
  return out;
}

function insertIntoBST(root: TreeNode | null, val: number): TreeNode {
  if (!root) return new TreeNode(val);
  if (val < root.val) root.left = insertIntoBST(root.left, val);
  else root.right = insertIntoBST(root.right, val);
  return root;
}
```

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

def _tree(level):
    if not level or level[0] is None:
        return None
    root = TreeNode(level[0]); q = [root]; i = 1
    while q and i < len(level):
        node = q.pop(0)
        if i < len(level) and level[i] is not None:
            node.left = TreeNode(level[i]); q.append(node.left)
        i += 1
        if i < len(level) and level[i] is not None:
            node.right = TreeNode(level[i]); q.append(node.right)
        i += 1
    return root

def _level(root):
    out, q = [], [root]
    while q:
        n = q.pop(0)
        if n:
            out.append(n.val); q.append(n.left); q.append(n.right)
        else:
            out.append(None)
    while out and out[-1] is None:
        out.pop()
    return out

def insert_into_bst(root, val):
    if not root:
        return TreeNode(val)
    if val < root.val:
        root.left = insert_into_bst(root.left, val)
    else:
        root.right = insert_into_bst(root.right, val)
    return root
```

## 6. Convert Sorted Array to Binary Search Tree (LeetCode 108)

**🟢 Easy.** Build a **height-balanced** BST from a sorted array.

```text
[-10,-3,0,5,9] → [0,-3,9,-10,null,5] (one valid answer)
```

**Approach.** The middle element becomes the root (so both halves have equal size); recursively build the left half and the right half. Several balanced answers are valid.

**Complexity.** O(n) time, O(log n) stack.

```typescript
class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}
function _tree(level: (number | null)[]): TreeNode | null {
  if (!level.length || level[0] === null) return null;
  const root = new TreeNode(level[0]); const q: TreeNode[] = [root]; let i = 1;
  while (q.length && i < level.length) {
    const node = q.shift()!;
    if (i < level.length && level[i] !== null) { node.left = new TreeNode(level[i]!); q.push(node.left); }
    i++;
    if (i < level.length && level[i] !== null) { node.right = new TreeNode(level[i]!); q.push(node.right); }
    i++;
  }
  return root;
}
function _level(root: TreeNode | null): (number | null)[] {
  const out: (number | null)[] = []; const q: (TreeNode | null)[] = [root];
  while (q.length) { const n = q.shift()!; if (n) { out.push(n.val); q.push(n.left, n.right); } else out.push(null); }
  while (out.length && out[out.length - 1] === null) out.pop();
  return out;
}

function sortedArrayToBST(nums: number[]): TreeNode | null {
  const build = (lo: number, hi: number): TreeNode | null => {
    if (lo > hi) return null;
    const mid = (lo + hi) >> 1;
    return new TreeNode(nums[mid], build(lo, mid - 1), build(mid + 1, hi));
  };
  return build(0, nums.length - 1);
}
```

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

def _tree(level):
    if not level or level[0] is None:
        return None
    root = TreeNode(level[0]); q = [root]; i = 1
    while q and i < len(level):
        node = q.pop(0)
        if i < len(level) and level[i] is not None:
            node.left = TreeNode(level[i]); q.append(node.left)
        i += 1
        if i < len(level) and level[i] is not None:
            node.right = TreeNode(level[i]); q.append(node.right)
        i += 1
    return root

def _level(root):
    out, q = [], [root]
    while q:
        n = q.pop(0)
        if n:
            out.append(n.val); q.append(n.left); q.append(n.right)
        else:
            out.append(None)
    while out and out[-1] is None:
        out.pop()
    return out

def sorted_array_to_bst(nums):
    def build(lo, hi):
        if lo > hi:
            return None
        mid = (lo + hi) // 2
        return TreeNode(nums[mid], build(lo, mid - 1), build(mid + 1, hi))
    return build(0, len(nums) - 1)
```