Binary Search Trees

Validation with bounds, inorder = sorted, LCA, deletion and balanced builds.

A binary search tree (BST) adds one invariant to a binary tree: every value in a node's left subtree is smaller than the node, and every value in its right subtree is larger. That invariant gives you two powers. You can discard half of the tree at each step, and an inorder traversal visits the values in sorted order.

Search, insert, and the O(h) cost

def search(node, target):
    while node and node.val != target:
        node = node.left if target < node.val else node.right
    return node

def insert(node, val):
    if node is None:
        return TreeNode(val)
    if val < node.val:
        node.left = insert(node.left, val)
    else:
        node.right = insert(node.right, val)
    return node

Both run in O(h). For a balanced BST that's O(log n), but inserting sorted data produces a linked list where h = n. Mention this. Production code uses self-balancing trees (red-black, AVL) or B-trees, and that's what sorted containers in Java (TreeMap) and C++ (std::map) are built on.

Validating a BST: pass bounds down

The classic trap is checking only left.val < node.val < right.val. That misses a deep node that violates an ancestor's bound.

def is_valid_bst(node, lo=float("-inf"), hi=float("inf")):
    if node is None:
        return True
    if not (lo < node.val < hi):
        return False
    return (is_valid_bst(node.left, lo, node.val) and
            is_valid_bst(node.right, node.val, hi))

An equally good alternative: an inorder traversal must be strictly increasing.

Inorder = sorted

Many BST questions are really "iterate the values in sorted order":

Kth smallest: inorder traversal, stop at the kth node.
Minimum absolute difference: compare each value with the previous one in inorder.
Two Sum in a BST: inorder into a sorted list, then use two pointers.
Recover a BST with two swapped nodes: find the inversions in the inorder sequence.

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

LCA is easier in a BST

You don't need to search both subtrees. Walk down from the root. If both values are smaller, go left. If both are larger, go right. Otherwise the current node is where they split.

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

Deletion

Deletion is the operation candidates fumble most. There are three cases:

Leaf: remove it.
One child: replace the node with its child.
Two children: copy the inorder successor (the smallest value in the right subtree) into the node, then delete that successor from the right subtree.

def delete(node, key):
    if node is None:
        return None
    if key < node.val:
        node.left = delete(node.left, key)
    elif key > node.val:
        node.right = delete(node.right, key)
    else:
        if node.left is None:
            return node.right
        if node.right is None:
            return node.left
        succ = node.right
        while succ.left:
            succ = succ.left
        node.val = succ.val
        node.right = delete(node.right, succ.val)
    return node

Building a balanced BST

From a sorted array, pick the middle element as the root and recurse on each half. The result has height O(log n). The same idea balances an existing BST: do an inorder traversal into a list, then rebuild.

[!INTERVIEW] Clarify duplicates Ask whether the tree can contain duplicate values and which side they go on. It changes the validation condition (< vs <=) and several follow-ups.

[!TIP] Practice Validate BST · Kth Smallest · LCA of a BST · Delete Node · Sorted Array to BST · Inorder Successor · Recover BST