Portfolio/Learn/Binary Search Trees: Search, Insert, Delete & Balance
Algorithms & DSIntermediate

Binary Search Trees: Search, Insert, Delete & Balance

Understand the BST invariant, implement core operations, and learn why balanced trees (AVL, Red-Black) guarantee O(log n) performance.

15 min read
March 14, 2026
BSTBinary SearchAVL TreeSelf-BalancingPython

The BST Invariant

A Binary Search Tree maintains one property: for every node, all values in the left subtree are smaller, and all values in the right subtree are larger. This enables O(h) search, insertion, and deletion where h is the tree height. For a balanced tree, h = O(log n).

Core Operations

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


def search_bst(root: TreeNode | None, target: int) -> TreeNode | None:
    if not root or root.val == target:
        return root
    if target < root.val:
        return search_bst(root.left, target)
    return search_bst(root.right, target)


def insert_bst(root: TreeNode | None, val: int) -> TreeNode:
    if not root:
        return TreeNode(val)
    if val < root.val:
        root.left = insert_bst(root.left, val)
    elif val > root.val:
        root.right = insert_bst(root.right, val)
    return root


def delete_bst(root: TreeNode | None, val: int) -> TreeNode | None:
    if not root:
        return None
    if val < root.val:
        root.left = delete_bst(root.left, val)
    elif val > root.val:
        root.right = delete_bst(root.right, val)
    else:
        # Node found — handle 3 cases
        if not root.left:
            return root.right
        if not root.right:
            return root.left
        # Two children: replace with inorder successor
        successor = root.right
        while successor.left:
            successor = successor.left
        root.val = successor.val
        root.right = delete_bst(root.right, successor.val)
    return root

BST deletion with two children uses the inorder successor (smallest in right subtree) or inorder predecessor (largest in left subtree). Both maintain the BST property.

Validating a BST

A common mistake is checking only parent-child relationships. A valid BST requires every node to be within a valid range defined by all its ancestors. Pass min/max bounds recursively.

python
def is_valid_bst(root: TreeNode | None) -> bool:
    def validate(node, min_val=float("-inf"), max_val=float("inf")):
        if not node:
            return True
        if node.val <= min_val or 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)

Kth Smallest Element

Inorder traversal of a BST yields elements in sorted order. To find the kth smallest, perform inorder and stop at the kth element. This runs in O(h + k) time.

python
def kth_smallest(root: TreeNode | None, k: int) -> int:
    stack = []
    curr = root

    while curr or stack:
        while curr:
            stack.append(curr)
            curr = curr.left
        curr = stack.pop()
        k -= 1
        if k == 0:
            return curr.val
        curr = curr.right

    return -1  # k is larger than tree size

Self-balancing BSTs (AVL trees, Red-Black trees) guarantee O(log n) height by rebalancing after each insertion/deletion. You rarely implement them from scratch, but understanding rotations helps with interview discussions and system design.

More Articles