Data Structures & Algorithms Cheatsheet

Binary Search Trees

Use this Data Structures & Algorithms reference while you build software engineering projects, review code, or refresh the syntax you reach for most.

Complexity

A BST keeps every left subtree below the node and every right subtree above it. Cost is proportional to the height, which is the whole story.

Operation	Balanced (h = log n)	Degenerate (h = n)
search	O(log n)	O(n)
insert	O(log n)	O(n)
delete	O(log n)	O(n)
find min or max	O(log n)	O(n)
predecessor or successor	O(log n)	O(n)
kth smallest	O(log n + k), O(log n) with size counts	O(n)
range query [lo, hi]	O(log n + k)	O(n)
inorder traversal (sorted output)	O(n)	O(n)
build from a sorted array	O(n)	O(n)

Inserting sorted data into an unbalanced BST produces a linked list, which is why production code uses a red-black tree (TreeMap, std::map) or an AVL tree. Self-balancing keeps h = O(log n) with rotations on insert and delete.

BST Versus Hash Map

Need	BST	Hash map
lookup by exact key	O(log n)	O(1) average
sorted iteration	free, inorder	O(n log n), must sort
min or max	O(log n)	O(n)
floor, ceiling, predecessor	O(log n)	not possible
range [lo, hi]	O(log n + k)	O(n)
worst-case guarantee	O(log n) balanced	O(n)

Reach for a balanced BST the moment the problem needs order: ranges, nearest neighbors, or a sorted view maintained under inserts.

Search, Insert, Delete

def search(root, target):
    """Iterative, O(h), O(1) space."""
    while root and root.val != target:
        root = root.left if target < root.val else root.right
    return root

def insert(root, val):
    """Returns the (possibly new) subtree root."""
    if not root:
        return TreeNode(val)
    if val < root.val:
        root.left = insert(root.left, val)
    elif val > root.val:
        root.right = insert(root.right, val)
    return root                      # equal: no duplicates, no change

def delete(root, key):
    """Three cases: leaf, one child, two children."""
    if not root:
        return None
    if key < root.val:
        root.left = delete(root.left, key)
    elif key > root.val:
        root.right = delete(root.right, key)
    else:
        if not root.left:
            return root.right        # 0 or 1 child
        if not root.right:
            return root.left
        succ = root.right            # two children: take the inorder successor
        while succ.left:
            succ = succ.left
        root.val = succ.val
        root.right = delete(root.right, succ.val)
    return root

def find_min(root):
    while root.left:
        root = root.left
    return root

def find_max(root):
    while root.right:
        root = root.right
    return root

Deletion with two children replaces the node's value with its inorder successor (the smallest node in the right subtree) and then deletes that successor, which by construction has at most one child. Using the inorder predecessor from the left subtree is equally valid.

// Java: TreeMap gives you all of this in O(log n), use it when allowed
TreeMap<Integer, String> t = new TreeMap<>();
t.put(5, "a");
t.floorKey(7);        // largest key <= 7
t.ceilingKey(7);      // smallest key >= 7
t.lowerKey(7);        // strictly less
t.higherKey(7);       // strictly greater
t.firstKey(); t.lastKey();
t.headMap(7); t.tailMap(7); t.subMap(2, true, 7, false);
t.pollFirstEntry();   // remove and return the smallest
TreeSet<Integer> s = new TreeSet<>();   // same navigation, no values

// C++ std::map and std::set are red-black trees
map<int, int> m;
auto it = m.lower_bound(7);      // first key >= 7
auto jt = m.upper_bound(7);      // first key > 7
if (it != m.begin()) { --it; }   // step back to get the floor
set<int> s;
s.insert(5);
distance(s.begin(), s.find(5));  // O(n), sets have no random access

Python has no balanced tree in the standard library. Use sortedcontainers (SortedList, SortedDict) where available, or a bisect-maintained list when inserts are rare enough that the O(n) shift is acceptable.

Validation

The common wrong answer compares each node only with its immediate children. A node deep in the left subtree can still exceed the root.

def is_valid_bst(root):
    """Pass down an open interval. O(n) time, O(h) space."""
    def go(node, low, high):
        if not node:
            return True
        if not (low < node.val < high):
            return False
        return (go(node.left, low, node.val)
                and go(node.right, node.val, high))
    return go(root, float("-inf"), float("inf"))

def is_valid_bst_inorder(root):
    """Inorder must be strictly increasing. Same O(n), constant extra state."""
    prev = None
    st, cur = [], root
    while cur or st:
        while cur:
            st.append(cur)
            cur = cur.left
        cur = st.pop()
        if prev is not None and cur.val <= prev:
            return False
        prev = cur.val
        cur = cur.right
    return True

Use float("-inf") and float("inf") rather than INT_MIN and INT_MAX, because a legitimate node value may equal the integer extreme.

Order Statistics And Ranges

Every one of these exploits the fact that inorder traversal of a BST is sorted, and that a comparison at each node prunes half the tree.

def kth_smallest(root, k):
    """Iterative inorder, stop at k. O(h + k)."""
    st, cur = [], root
    while cur or st:
        while cur:
            st.append(cur)
            cur = cur.left
        cur = st.pop()
        k -= 1
        if k == 0:
            return cur.val
        cur = cur.right
    return -1

def range_sum(root, lo, hi):
    """Sum of values in [lo, hi]. Prune subtrees that cannot contribute."""
    if not root:
        return 0
    if root.val < lo:
        return range_sum(root.right, lo, hi)
    if root.val > hi:
        return range_sum(root.left, lo, hi)
    return (root.val
            + range_sum(root.left, lo, hi)
            + range_sum(root.right, lo, hi))

def lca_bst(root, p, q):
    """LCA in a BST is O(h), no recursion into both sides needed."""
    while root:
        if p.val < root.val and q.val < root.val:
            root = root.left
        elif p.val > root.val and q.val > root.val:
            root = root.right
        else:
            return root            # the split point
    return None

def closest_value(root, target):
    """On a tie the smaller value wins, which LeetCode 270 requires."""
    best = root.val
    while root:
        d, bd = abs(root.val - target), abs(best - target)
        if d < bd or (d == bd and root.val < best):
            best = root.val
        root = root.left if target < root.val else root.right
    return best

def inorder_successor(root, p):
    """Smallest value strictly greater than p.val."""
    succ = None
    while root:
        if p.val < root.val:
            succ = root            # candidate, look for something smaller
            root = root.left
        else:
            root = root.right
    return succ

Building And Rebalancing

def sorted_array_to_bst(a):
    """Height-balanced by construction. O(n)."""
    def build(lo, hi):
        if lo > hi:
            return None
        mid = (lo + hi) // 2
        node = TreeNode(a[mid])
        node.left = build(lo, mid - 1)
        node.right = build(mid + 1, hi)
        return node
    return build(0, len(a) - 1)

def bst_from_preorder(pre):
    """O(n) with bounds, no repeated searching."""
    it = iter(pre)
    def build(bound):
        nonlocal nxt
        if nxt is None or nxt > bound:
            return None
        node = TreeNode(nxt)
        nxt = next(it, None)
        node.left = build(node.val)
        node.right = build(bound)
        return node
    nxt = next(it, None)
    return build(float("inf"))

def balance(root):
    """Flatten to a sorted list, rebuild. O(n)."""
    vals = []
    def walk(n):
        if n:
            walk(n.left)
            vals.append(n.val)
            walk(n.right)
    walk(root)
    return sorted_array_to_bst(vals)

AVL And Red-Black At A Glance

You rarely implement these, but interviewers ask what keeps a tree balanced.

Property	AVL	Red-black
balance invariant	heights differ by ≤ 1	no two red nodes adjacent, equal black height
height bound	≤ 1.44 log n	≤ 2 log n
lookups	faster, tighter balance	slightly slower
insert and delete	more rotations	fewer rotations
used by	in-memory indexes, some databases	`TreeMap`, `std::map`, Linux schedulers

Both fix violations with rotations, an O(1) pointer rewiring that changes the local shape while preserving the inorder sequence.

Gotchas

Validation needs a range, not a local comparison. Comparing a node only with its children passes invalid trees.
Duplicates are undefined by default. Decide the policy: reject, always go right, or store a count in the node. Say it out loud in an interview.
INT_MIN and INT_MAX as sentinels fail when a node holds exactly that value. Use infinities or a "prev pointer" inorder check.
Insert must return the subtree root and the caller must reassign. insert(root.left, v) without root.left = silently does nothing on an empty child.
Delete has three cases. Skipping the one-child case leaves the tree corrupted rather than throwing.
Sorted input degenerates the tree. If keys arrive in order, insert from the middle out, or use a balanced structure.
kth smallest under frequent updates wants a size field per node, so the query stays O(log n) instead of O(h + k).
C++ set has no index access. distance(s.begin(), it) is O(n), so it is not a substitute for an order-statistic tree.