Search in structures

A binary search tree keeps smaller keys on the left and larger keys on the right, so a lookup is binary search on a linked structure: compare, then go left or right.

The cost is O(h) for tree height h. A balanced tree such as Java's TreeMap (a red-black tree) guarantees O(log n). An unbalanced BST built from sorted input degenerates into a list with O(n) lookups.

1Node find(Node root, int key) {
2    Node cur = root;
3    while (cur != null && cur.key != key) {
4        cur = key < cur.key ? cur.left : cur.right;
5    }
6    return cur;   // null if absent
7}

A hash table computes hash(key) to jump straight to a bucket, so expected lookup is O(1) regardless of n. Java's HashMap and HashSet work this way and need consistent equals() and hashCode().

Hashing gives up order: there are no floor, ceiling or range queries. Adversarial or poorly distributed keys raise collision costs. Since Java 8, HashMap turns long collision chains into trees, bounding the worst case at O(log n) per bucket.

A heap only guarantees that each parent is ordered relative to its children. That makes reading the minimum (or maximum) O(1), but says nothing about where any other value is, so contains must scan: PriorityQueue.contains is O(n).

If you need both priority access and fast membership, pair the heap with a HashSet or HashMap of positions, which is how indexed priority queues for Dijkstra work.

A trie stores strings character by character along tree edges. Looking up a word or checking a prefix takes O(L) for a string of length L, independent of how many words are stored.

Tries power autocomplete and spell-checkers, and they make “all words with prefix p” queries natural, which hash tables cannot do.

1boolean startsWith(TrieNode root, String prefix) {
2    TrieNode cur = root;
3    for (char c : prefix.toCharArray()) {
4        cur = cur.children[c - 'a'];
5        if (cur == null) return false;
6    }
7    return true;
8}

“Can I get from A to B?” is a search over a graph instead of a list. Breadth-first search (BFS) or depth-first search (DFS) visits each vertex and edge at most once, in O(V + E).

Track visited vertices, because graphs can contain cycles. BFS also returns the fewest-edges path in an unweighted graph.

1boolean reachable(List<List<Integer>> adj, int src, int dst) {
2    boolean[] seen = new boolean[adj.size()];
3    Deque<Integer> queue = new ArrayDeque<>(List.of(src));
4    seen[src] = true;
5    while (!queue.isEmpty()) {
6        int u = queue.poll();
7        if (u == dst) return true;
8        for (int v : adj.get(u)) {
9            if (!seen[v]) { seen[v] = true; queue.add(v); }
10        }
11    }
12    return false;
13}