Binary Search Trees

The invariant

A binary search tree is a binary tree where for every node:

all values in the left subtree < node.val < all values in the right subtree

(Some definitions allow duplicates on one side — clarify in interviews.)

Consequences:

• In-order traversal visits values in sorted order. This is the most useful fact about BSTs.
• Search, insert and delete follow one root-to-leaf path: O(h).
• If the tree is balanced, h = O(log n). If you insert sorted data into a plain BST, it degenerates into a linked list and h = n.

Search and insert

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

def insert(root, val):
    if not root:
        return TreeNode(val)
    if val < root.val:
        root.left = insert(root.left, val)
    else:
        root.right = insert(root.right, val)
    return root

TreeNode* searchBST(TreeNode* root, int target) {
    while (root && root->val != target)
        root = target < root->val ? root->left : root->right;
    return root;
}
TreeNode* insertIntoBST(TreeNode* root, int val) {
    if (!root) return new TreeNode(val);
    if (val < root->val) root->left = insertIntoBST(root->left, val);
    else root->right = insertIntoBST(root->right, val);
    return root;
}

Delete

Three cases:

1. Leaf: remove it.
2. One child: replace the node with its child.
3. Two children: replace its value with the in-order successor (smallest in the right subtree), then delete that successor from the right subtree.

def delete_node(root, key):
    if not root:
        return None
    if key < root.val:
        root.left = delete_node(root.left, key)
    elif key > root.val:
        root.right = delete_node(root.right, key)
    else:
        if not root.left:
            return root.right
        if not root.right:
            return root.left
        succ = root.right
        while succ.left:
            succ = succ.left
        root.val = succ.val
        root.right = delete_node(root.right, succ.val)
    return root

Validate a BST

Checking only left.val < node.val < right.val is wrong — the constraint applies to the whole subtree. Pass bounds down:

def is_valid_bst(root):
    def ok(node, low, high):
        if not node:
            return True
        if not (low < node.val < high):
            return False
        return ok(node.left, low, node.val) and ok(node.right, node.val, high)
    return ok(root, float("-inf"), float("inf"))

bool ok(TreeNode* n, long long low, long long high) {
    if (!n) return true;
    if (n->val <= low || n->val >= high) return false;
    return ok(n->left, low, n->val) && ok(n->right, n->val, high);
}
bool isValidBST(TreeNode* root) { return ok(root, LLONG_MIN, LLONG_MAX); }

Alternative: an in-order traversal must be strictly increasing.

In-order tricks

k-th smallest

def kth_smallest(root, k):
    stack, cur = [], root
    while True:
        while cur:
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()
        k -= 1
        if k == 0:
            return cur.val
        cur = cur.right

If k-th queries are frequent and the tree changes, store subtree sizes in each node — then k-th is O(h) (an order-statistic tree).

BST iterator

The iterative in-order, split into next() calls — O(h) memory, O(1) amortized per call:

class BSTIterator:
    def __init__(self, root):
        self.stack = []
        self._push_left(root)
    def _push_left(self, node):
        while node:
            self.stack.append(node)
            node = node.left
    def next(self):
        node = self.stack.pop()
        self._push_left(node.right)
        return node.val
    def hasNext(self):
        return bool(self.stack)

A forward and a reverse iterator together give two pointers on a BST (Two Sum IV).

Recover a BST with two swapped nodes

In-order of a BST with two swapped values has one or two “drops” (prev > cur). The first wrong node is prev at the first drop; the second is cur at the last drop. Swap their values.

Floor, ceiling, and range queries

def floor(root, x):               # largest value <= x
    best = None
    while root:
        if root.val == x:
            return x
        if root.val < x:
            best = root.val
            root = root.right
        else:
            root = root.left
    return best

Range sum / range listing: recurse only into subtrees that can intersect [lo, hi].

Building balanced BSTs

From a sorted array: the middle element becomes the root, recursively.

def sorted_array_to_bst(nums, lo=0, hi=None):
    if hi is None:
        hi = len(nums) - 1
    if lo > hi:
        return None
    mid = (lo + hi) // 2
    root = TreeNode(nums[mid])
    root.left = sorted_array_to_bst(nums, lo, mid - 1)
    root.right = sorted_array_to_bst(nums, mid + 1, hi)
    return root

Self-balancing BSTs (and what to actually use)

AVL trees, red-black trees, treaps and splay trees rebalance with rotations to keep h = O(log n). You won't implement them in interviews, but you'll use them constantly via libraries:

set<int> s = {1, 5, 9};
auto it = s.lower_bound(6);       // → 9 (first >= 6)
if (it != s.begin()) {
    int predecessor = *prev(it);  // → 5 (largest < 6)
}
multiset<int> ms; ms.erase(ms.find(5));   // erase ONE copy (ms.erase(5) erases all)

from sortedcontainers import SortedList
sl = SortedList([1, 5, 9])
i = sl.bisect_left(6)             # 2
succ = sl[i] if i < len(sl) else None       # 9
pred = sl[i - 1] if i > 0 else None         # 5
sl.add(7); sl.remove(5)

Typical uses: sliding window median, contains duplicate III (nearest value in a window), my calendar, stock price fluctuation, maintaining a leaderboard.

Complexity

Common mistakes

• Validating with only the immediate children.
• int bounds overflowing on extreme node values.
• Forgetting to return the (possibly new) root from recursive insert/delete.
• multiset::erase(value) removing all copies.