IntermediateTrees

BST Operations

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

Time: O(h)
Space: O(h)
Pattern Overview

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.

General Recognition Cues
General indicators that this pattern might be applicable
  • Validate BST
  • kth smallest
  • Insert/delete
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)
Code Templates
Compare implementations across different languages
def template(*args, **kwargs):
    # General template placeholder
    pass
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