Binary Search Tree Operations: Validate BST, Search, Insert, Delete, and Kth Smallest

Why BST operations show up so often in interviews

Binary search trees are one of those topics that look simple on paper and still expose a lot about how you think. Interviewers use BST problems to check whether you understand recursion, traversal order, invariants, and how to reason about state as you move through a tree.

If you can handle common BST operations cleanly, you can solve a wide range of interview questions:

• validate whether a tree is a valid BST
• search for a value efficiently
• insert and delete nodes correctly
• find the kth smallest element
• reason about in-order traversal and subtree bounds

The pattern matters because a BST gives you structure. A lot of problems become easier once you remember the core rule: everything in the left subtree is smaller, everything in the right subtree is larger. The details matter, though. Many bugs come from only checking a node against its immediate children instead of all ancestors.

Problem statement

A binary search tree is a binary tree with this property:

• left subtree values are strictly less than the node value
• right subtree values are strictly greater than the node value

Depending on the problem, duplicates may be disallowed or handled in a specific direction. In interviews, always clarify that detail.

Common BST tasks include:

1. Validate BST: determine whether a tree satisfies the BST property.
2. Search BST: find whether a target exists.
3. Insert into BST: place a new value while preserving the property.
4. Delete from BST: remove a node and keep the tree valid.
5. Kth smallest in BST: return the kth smallest value, usually using in-order traversal.

These operations show up individually, but they also build on the same intuition.

Intuition and insight

The biggest mental shift is this:

A BST node is constrained by more than its parent

Suppose you have this tree:

      10
     /  \
    5    15
        /  \
       6    20

At first glance, every parent-child relationship looks fine. But 6 is in the right subtree of 10, so it must be greater than 10. It is not. That means the tree is invalid.

This is why validation must carry bounds downward through recursion:

• every node in the left subtree must be in the range (low, current_value)
• every node in the right subtree must be in the range (current_value, high)

For traversal-based questions like kth smallest, the key insight is different:

In-order traversal of a BST returns values in sorted order

That makes a lot of problems easier. If you traverse left, visit node, then right, you see the values in ascending order. You can stop early once you reach the kth element.

For search, insert, and delete, the BST property lets you ignore half the tree at each step, which is why these operations are typically O(h) where h is the tree height.

Approach 1: Validate BST using bounds

This is the most important BST interview pattern.

Idea

Recursively check that each node lies within a valid interval.

• The root can be anything: (-inf, inf)
• Left child narrows the upper bound to the current node value
• Right child narrows the lower bound to the current node value

Python code

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


def is_valid_bst(root: TreeNode) -> bool:
    def dfs(node, low, high):
        if not node:
            return True

        if not (low < node.val < high):
            return False

        return dfs(node.left, low, node.val) and dfs(node.right, node.val, high)

    return dfs(root, float('-inf'), float('inf'))

Worked example 1

Consider this tree:

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

Walkthrough:

• Start at 8 with bounds (-inf, inf) → valid
• Left subtree of 8 must be in (-inf, 8)
  • 3 fits
  • left of 3 must be in (-inf, 3) → 1 fits
  • right of 3 must be in (3, 8) → 6 fits
    • left of 6 must be in (3, 6) → 4 fits
    • right of 6 must be in (6, 8) → 7 fits
• Right subtree of 8 must be in (8, inf)
  • 10 fits
  • right of 10 must be in (10, inf) → 14 fits
  • left of 14 must be in (10, 14) → 13 fits

Every node satisfies its range, so the tree is a valid BST.

Worked example 2: invalid tree

      10
     /  \
    5    15
        /  \
       6    20

Trace:

• 10 valid in (-inf, inf)
• 15 valid in (10, inf)
• 6 is in the left subtree of 15, so it must be in (10, 15)
• But 6 is not greater than 10, so the tree fails

This example shows why local checks are not enough.

Approach 2: Search, insert, and delete

These operations all use the same core navigation rule.

Search BST

At each step:

• if target equals current value, return the node
• if target is smaller, go left
• if target is larger, go right

def search_bst(root: TreeNode, target: int) -> TreeNode:
    cur = root
    while cur:
        if cur.val == target:
            return cur
        elif target < cur.val:
            cur = cur.left
        else:
            cur = cur.right
    return None

Insert into BST

Insertion follows the same path as search until you find a null spot.

def insert_bst(root: TreeNode, val: int) -> TreeNode:
    if not root:
        return TreeNode(val)

    if val < root.val:
        root.left = insert_bst(root.left, val)
    else:
        root.right = insert_bst(root.right, val)

    return root

Delete from BST

Deletion is the trickiest BST operation because you have to preserve structure in three cases:

1. Node has no children: remove it directly.
2. Node has one child: replace the node with its child.
3. Node has two children: replace the node with its inorder successor or predecessor, then delete that replacement node.

The inorder successor is the smallest node in the right subtree.

def delete_bst(root: TreeNode, key: int) -> TreeNode:
    if not root:
        return None

    if key < root.val:
        root.left = delete_bst(root.left, key)
    elif key > root.val:
        root.right = delete_bst(root.right, key)
    else:
        # Case 1 and 2: zero or one child
        if not root.left:
            return root.right
        if not root.right:
            return root.left

        # Case 3: two children
        successor = root.right
        while successor.left:
            successor = successor.left

        root.val = successor.val
        root.right = delete_bst(root.right, successor.val)

    return root

Worked example 3: deleting a node with two children

Suppose you delete 5 from this BST:

        8
       / \
      5   12
     / \  / \
    3  7 10  14

Steps:

• 5 has two children: 3 and 7
• Find the inorder successor of 5, which is 7
• Replace 5 with 7
• Delete the original 7 from the right subtree

Result:

        8
       / \
      7   12
     / \  / \
    3  - 10  14

The exact shape can vary depending on implementation, but the BST property remains intact.

Approach 3: Kth smallest element with in-order traversal

Since in-order traversal gives values in sorted order, you can count nodes as you visit them.

Recursive solution

def kth_smallest(root: TreeNode, k: int) -> int:
    count = 0
    answer = None

    def inorder(node):
        nonlocal count, answer
        if not node or answer is not None:
            return

        inorder(node.left)
        count += 1
        if count == k:
            answer = node.val
            return
        inorder(node.right)

    inorder(root)
    return answer

Iterative solution

This is often cleaner in interviews because it avoids recursion depth concerns.

def kth_smallest_iter(root: TreeNode, k: int) -> int:
    stack = []
    cur = root

    while stack or cur:
        while cur:
            stack.append(cur)
            cur = cur.left

        cur = stack.pop()
        k -= 1
        if k == 0:
            return cur.val

        cur = cur.right

How it works

For this BST:

      5
     / \
    3   6
   / \
  2   4
 /
1

The in-order sequence is:

1, 2, 3, 4, 5, 6

So:

• k = 1 → 1
• k = 3 → 3
• k = 5 → 5

The traversal order itself is the solution.

Complexity analysis

BST performance depends heavily on tree height.

Balanced vs unbalanced BSTs

This is why interviewers sometimes ask follow-up questions about balancing, AVL trees, or red-black trees.

Common mistakes

A few BST bugs show up again and again:

• Only checking parent-child order instead of full ancestor bounds
• Forgetting duplicates policy and using <= or >= incorrectly
• Mixing up inorder successor and predecessor during delete
• Not stopping early in kth smallest traversal
• Assuming the tree is balanced when analyzing runtime

If you can explain these clearly, you usually sound much stronger in an interview.

Related problems

Once you understand BST operations, a lot of adjacent problems become easier:

• Validate Binary Search Tree
• Lowest Common Ancestor in a BST
• Kth Smallest Element in a BST
• Convert Sorted Array to BST
• Delete Node in a BST
• Inorder Successor in BST
• Range Sum of BST
• Trim a Binary Search Tree

A good next step is to practice problems that combine traversal with invariants.

Key takeaways

• A BST node is constrained by all ancestors, not just its parent.
• Validation is easiest with recursive bounds.
• Search, insert, and delete all follow the same left/right decision rule.
• In-order traversal gives sorted order in a BST.
• Kth smallest is usually just in-order traversal with counting.
• Balanced trees make BST operations fast; skewed trees do not.

If you want to see the bounds, traversal order, and subtree updates live as you step through examples, check out codebrew.ai.

Practice these next

1. Validate Binary Search Tree
2. Kth Smallest Element in a BST
3. Delete Node in a BST
4. Lowest Common Ancestor of a BST
5. Range Sum of BST