Binary Search Tree

Intuition

A binary search tree (BST) is a binary tree with an ordering rule: for every node, all keys in its left subtree are smaller than its key, and all keys in its right subtree are larger. The rule holds for whole subtrees, not just direct children, and it has one beautiful consequence: an in-order traversal (left, node, right) visits the keys in sorted order.

Every operation is a walk from the root that discards half of the remaining tree at each step, like binary search on a sorted array:

• Search: go left if the target is smaller, right if larger.
• Insert: search until you fall off the tree, and hang the new node there.
• Delete: a leaf is simply removed; a node with one child is replaced by that child; a node with two children takes the key of its in-order successor (the minimum of its right subtree), and then that successor is deleted from the right subtree.
• Min / max: follow left (or right) pointers to the end.
• Floor / ceiling (largest key <= x, smallest key >= x): walk down and remember the last node that went the right way.
• k-th smallest / rank: an in-order walk that stops early, or O(h) if every node stores its subtree size.

All of these cost O(h), where h is the height. A random insertion order gives an expected height of O(log n), but inserting sorted keys produces a chain with h = n, and every operation degrades to O(n).

Balanced BSTs prevent that by restructuring the tree with rotations: local moves that re-hang three subtrees while keeping the in-order sequence unchanged. Different trees use different invariants:

• AVL trees keep the heights of every node's two subtrees within 1 of each other, which bounds the height by about 1.44 * log2(n).
• Red-black trees color nodes so that no red node has a red child and every root-to-leaf path has the same number of black nodes, which bounds the height by 2 * log2(n + 1). They rebalance with fewer rotations and back Java's TreeMap/TreeSet and C++'s std::map/std::set.

Interviews almost never ask you to implement AVL or red-black insertion and deletion. What they test is the plain BST operations above and whether you know when to reach for an ordered map from the standard library.

When to use it in interviews / OAs

• The input is a BST: validate it, search/insert/delete, find the k-th smallest, the lowest common ancestor (the first node whose key lies between the two targets), range sums with pruning, trimming to a range, recovering two swapped nodes, building a balanced BST from a sorted array.
• You need an ordered set or map: floor/ceiling or predecessor/successor on a changing set (nearby values within a distance, interval booking without overlaps, the closest earlier timestamp), ranks on a leaderboard, sliding-window order statistics.
• Sorted iteration with early exit: in-order traversal with an explicit stack (BST iterator, two-sum on a BST with forward and backward iterators).

Library equivalents:

• Java: TreeMap / TreeSet with floorKey, ceilingKey, lowerKey, higherKey, headMap, tailMap, pollFirst.
• C++: std::set / std::map / std::multiset with lower_bound, upper_bound, and iterator prev/next.
• Python: there is no balanced BST in the standard library. Options: bisect on a sorted list (O(log n) search, O(n) but very fast insert/delete), sortedcontainers.SortedList where it is available (it is on LeetCode), a heap with lazy deletion if you only need the min or max, or a Fenwick tree over compressed values for ranks.

Template

Search, insert and delete. The recursive insert/delete return the (possibly new) root of each subtree, and the caller re-attaches it; forgetting that assignment is the classic bug.

from typing import Optional


class TreeNode:
    def __init__(self, key: int, left: "Optional[TreeNode]" = None, right: "Optional[TreeNode]" = None) -> None:
        self.key, self.left, self.right = key, left, right


def search(root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
    while root and root.key != key:
        root = root.left if key < root.key else root.right  # Discard the half that cannot contain key.
    return root


def insert(root: Optional[TreeNode], key: int) -> TreeNode:
    if root is None:
        return TreeNode(key)
    if key < root.key:
        root.left = insert(root.left, key)  # Re-attach the (possibly new) subtree root.
    elif key > root.key:
        root.right = insert(root.right, key)
    return root  # Duplicates are ignored in this version.


def delete(root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
    if root is None:
        return None
    if key < root.key:
        root.left = delete(root.left, key)
    elif key > root.key:
        root.right = delete(root.right, key)
    else:
        if root.left is None:  # Zero or one child: splice the node out.
            return root.right
        if root.right is None:
            return root.left
        succ = root.right  # Two children: copy the in-order successor (min of the right subtree).
        while succ.left:
            succ = succ.left
        root.key = succ.key
        root.right = delete(root.right, succ.key)  # Then delete that successor from the right subtree.
    return root


def inorder(root: Optional[TreeNode]) -> list[int]:
    return inorder(root.left) + [root.key] + inorder(root.right) if root else []


root = None
for k in (5, 3, 8, 2, 4, 7, 9):
    root = insert(root, k)
assert inorder(root) == [2, 3, 4, 5, 7, 8, 9] and search(root, 4).key == 4 and search(root, 6) is None
root = delete(root, 5)  # The root has two children.
assert inorder(root) == [2, 3, 4, 7, 8, 9] and root.key == 7

The queries interviewers like most. Validation must pass bounds down from all ancestors; comparing a node only with its children misses violations deeper in the tree. (These reuse the TreeNode and insert from above.)

def is_valid_bst(root: Optional[TreeNode], lo: float = float("-inf"), hi: float = float("inf")) -> bool:
    # Every key must lie strictly between bounds inherited from all its ancestors.
    if root is None:
        return True
    if not lo < root.key < hi:
        return False
    return is_valid_bst(root.left, lo, root.key) and is_valid_bst(root.right, root.key, hi)


def kth_smallest(root: Optional[TreeNode], k: int) -> int:
    # Iterative in-order traversal that stops after k keys; assumes 1 <= k <= size.
    stack: list[TreeNode] = []
    while True:
        while root:  # Walk as far left as possible.
            stack.append(root)
            root = root.left
        root = stack.pop()  # The next key in sorted order.
        k -= 1
        if k == 0:
            return root.key
        root = root.right


def floor_ceiling(root: Optional[TreeNode], x: int) -> tuple[Optional[int], Optional[int]]:
    # (largest key <= x, smallest key >= x); None when it does not exist.
    floor = ceil = None
    while root:
        if root.key == x:
            return x, x
        if root.key < x:
            floor = root.key  # A candidate; a closer one can only be to the right.
            root = root.right
        else:
            ceil = root.key
            root = root.left
    return floor, ceil


root = None
for k in (8, 3, 10, 1, 6, 14):
    root = insert(root, k)
assert is_valid_bst(root) and kth_smallest(root, 3) == 6
assert floor_ceiling(root, 7) == (6, 8) and floor_ceiling(root, 0) == (None, 1)
assert not is_valid_bst(TreeNode(5, TreeNode(1), TreeNode(6, TreeNode(4))))  # 4 sits right of 5.

A rotation, the building block of every balanced BST. It changes the shape (and the height) but not the sorted order.

def rotate_right(a: TreeNode) -> TreeNode:
    #       a            b
    #      / \          / \
    #     b   T3  ->  T1   a
    #    / \              / \
    #   T1  T2          T2  T3
    b = a.left
    a.left = b.right  # T2 changes parent; in-order order is unchanged.
    b.right = a
    return b  # The caller re-attaches b where a used to hang.


def rotate_left(a: TreeNode) -> TreeNode:  # Mirror image of rotate_right.
    b = a.right
    a.right = b.left
    b.left = a
    return b


chain = TreeNode(3, TreeNode(2, TreeNode(1)))  # A left-leaning chain of height 3.
root = rotate_right(chain)
assert root.key == 2 and root.left.key == 1 and root.right.key == 3 and inorder(root) == [1, 2, 3]

In Python, a sorted list plus bisect is often the most practical "ordered set" in an interview: the code is short, and the O(n) insert is a single memory move that stays fast up to around 10^5 elements.

import bisect


class SortedSet:
    # Stdlib-only ordered set on a sorted list: O(log n) search, O(n) insert/delete.
    def __init__(self) -> None:
        self.a: list[int] = []

    def add(self, x: int) -> None:
        i = bisect.bisect_left(self.a, x)
        if i == len(self.a) or self.a[i] != x:
            self.a.insert(i, x)  # A fast memmove, fine for about 10^5 elements.

    def remove(self, x: int) -> None:
        i = bisect.bisect_left(self.a, x)
        if i < len(self.a) and self.a[i] == x:
            self.a.pop(i)

    def floor(self, x: int) -> int | None:  # Largest element <= x.
        i = bisect.bisect_right(self.a, x)
        return self.a[i - 1] if i else None

    def ceiling(self, x: int) -> int | None:  # Smallest element >= x.
        i = bisect.bisect_left(self.a, x)
        return self.a[i] if i < len(self.a) else None


s = SortedSet()
for x in (10, 4, 7):
    s.add(x)
assert s.floor(8) == 7 and s.ceiling(8) == 10 and s.floor(3) is None
s.remove(7)
assert s.floor(8) == 4

Complexity

Operation	Plain BST	Balanced BST / library ordered map
search, insert, delete, floor/ceiling	O(h), worst O(n)	O(log n)
min / max	O(h)	O(log n) (O(1) with cached ends)
in-order traversal	O(n)	O(n)
k-th smallest	O(h + k), or O(h) with subtree sizes	O(log n) with order statistics

Space is O(n) for the nodes, plus O(h) for recursion or the explicit stack.

Common pitfalls

• Validating locally. left.key < node.key < right.key at every node is not enough; carry (low, high) bounds, or check that the in-order sequence is strictly increasing.
• Duplicate keys. Decide the policy up front: reject them, keep a count per node, or always send equal keys to one side (and be consistent in search and validation).
• Sentinel bounds in Java/C++. Using INT_MIN/INT_MAX as bounds fails when keys equal those values; use null, long, or explicit flags.
• Losing subtrees. In recursive insert/delete, always assign the returned subtree (root.left = insert(root.left, key)).
• Deleting the wrong successor. After copying the successor's key, delete it from the right subtree, not from the whole tree.
• Assuming balance. Unless the problem says so, a given BST may be a chain; state complexities in terms of h and avoid deep recursion in Python (convert to iteration when the tree can be 10^4+ deep).
• Hand-rolling a balanced tree in an interview. Say which library structure you would use; implement AVL or red-black logic only if explicitly asked.

Interview variations

• Validate a BST, recover a BST with two swapped nodes (find the one or two inversions in the in-order sequence).
• k-th smallest element, BST iterator (a stack holding the left spine; next is amortized O(1) with O(h) memory).
• Lowest common ancestor of a BST, closest value and k closest values.
• Insert / delete / search, trim a BST to [low, high], range sum of a BST (prune subtrees outside the range).
• Convert a sorted array or list to a height-balanced BST (pick the middle as the root, recurse).
• Two sum in a BST (in-order list plus two pointers, or two iterators).
• Serialize and deserialize a BST: a preorder list is enough, because the ordering rule tells you where each subtree ends.
• Ordered-map problems: values within distance t inside a window of size k, non-overlapping booking calendar, sliding window median, stock price records with corrections.