CodeMosa

Master LeetCode Patterns

IntermediateTreesRead Trees Fundamentals →

BST Operations

Validate BST, search/insert/delete, and transform BSTs

Time: O(h)
Space: O(h)

What is BST Operations?

#
Definition: Use the BST ordering invariant (left < root < right) to validate, search/insert/delete, and perform ordered queries.

Core Idea

#

BST invariant (left < root < right) enables ordered traversal, rank queries, and structural updates.

When to Use

#

Use when order-based queries/updates are needed with tree structure.

How BST Operations works

#

Bounded DFS validation using min/max ranges and standard BST search/insert/delete leveraging the BST ordering invariant.

  • Validate BST
  • kth smallest
  • Insert/delete

General Recognition Cues

#
General indicators that this pattern might be applicable
  • Validate BST
  • kth smallest
  • Insert/delete

Code Templates

#
Bounded DFS validation using min/max ranges and standard BST search/insert/delete leveraging the BST ordering invariant.
# BST Templates
def is_valid_bst(root):
    def dfs(n, lo, hi):
        if not n: return True
        if not (lo < n.val < hi): return False
        return dfs(n.left, lo, n.val) and dfs(n.right, n.val, hi)
    return dfs(root, float('-inf'), float('inf'))

def bst_search(root, key):
    cur=root
    while cur:
        if key==cur.val: return cur
        cur = cur.left if key<cur.val else cur.right
    return None

Pattern Variants & Approaches

#
Different methodologies and implementations for this pattern
1

Validate

#

Check bounds during DFS

When to Use This Variant
  • Min/max bounds
Use Case
Correctness check
Advantages
  • Linear time
  • Simple
Implementation
def is_valid_bst(root):
    def dfs(node, lo, hi):
        if not node: return True
        if not (lo < node.val < hi): return False
        return dfs(node.left, lo, node.val) and dfs(node.right, node.val, hi)
    return dfs(root, float('-inf'), float('inf'))
2

kth Smallest

#

Inorder traversal counting nodes

When to Use This Variant
  • Inorder index
Use Case
Order-stat
Advantages
  • O(h+k)
  • No extra space if iterative
Implementation
def kth_smallest(root, k):
    st=[]; node=root
    while st or node:
        while node: st.append(node); node=node.left
        node=st.pop(); k-=1
        if k==0: return node.val
        node=node.right
3

Insert/Delete

#

Recursive updates preserving BST

When to Use This Variant
  • BST mutation
Use Case
CRUD ops
Advantages
  • O(h)
Implementation
def bst_insert(root, val):
    if not root: return TreeNode(val)
    if val < root.val: root.left = bst_insert(root.left, val)
    elif val > root.val: root.right = bst_insert(root.right, val)
    return root
def bst_delete(root, key):
    if not root: return None
    if key < root.val: root.left = bst_delete(root.left, key)
    elif key > root.val: root.right = bst_delete(root.right, key)
    else:
        if not root.left: return root.right
        if not root.right: return root.left
        # replace with successor
        s = root.right
        while s.left: s = s.left
        root.val = s.val
        root.right = bst_delete(root.right, s.val)
    return root
4

Transform

#

Greater sum tree/morph operations

When to Use This Variant
  • Reverse inorder
Use Case
Augmentation
Advantages
  • Inorder accumulation
Implementation
def convert_bst(root):
    acc = 0
    def dfs(node):
        nonlocal acc
        if not node: return
        dfs(node.right)
        acc += node.val; node.val = acc
        dfs(node.left)
    dfs(root); return root

Common Pitfalls

#
Watch out for these common mistakes
  • Integer overflow on bounds
  • Not handling duplicates policy
  • Deletion cases (0/1/2 children)

Related Patterns

#
Lowest Common AncestorTree BFSTree DFS (Depth-First Search)Trie

Example Problems

#
Classic LeetCode problems using this pattern

Complexity Analysis

#
Time Complexity
O(h)

Operations cost proportional to height.

Space Complexity
O(h)

Recursion/stack depth = height.

Ready to test your knowledge?

Test your pattern recognition with interactive questions