Data Structures & Algorithms Cheatsheet

Tries

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

Complexity

A trie (prefix tree) stores strings by their characters, one edge per character. Cost depends on the word length, not the number of stored words.

Operation	Time	Space
insert a word of length m	O(m)	O(m) new nodes worst case
search exact word	O(m)	O(1)
prefix exists	O(m)	O(1)
delete a word	O(m)	O(1)
all words with a prefix	O(m + k)	O(k) for the output
count words with a prefix	O(m) with a counter per node	O(1)
build from n words	O(n · m)	O(n · m · Σ) worst case
wildcard match with `.`	O(Σ^d · m)	O(m) recursion

Σ is the alphabet size (26 for lowercase English). Space is the weak point: a fixed 26-slot array per node wastes memory on sparse tries, so a hash map per node is usually better.

When To Reach For A Trie

Prefix queries. "All words starting with pre", autocomplete, IP routing tables.
Many searches against a fixed dictionary. Build once in O(total characters), then each query is O(m) with no dependence on dictionary size.
Shared prefixes are common. A trie compresses them, so 10,000 words sharing inter store it once.
Word-search-in-grid problems. A trie prunes DFS the moment the current path stops being any word's prefix.
Maximum XOR pairs. A binary trie over bits solves it in O(32n) instead of O(n²).

A hash set answers "is this an exact word" just as fast. Use a trie only when prefixes matter.

Basic Implementation

class TrieNode:
    __slots__ = ("children", "is_word")

    def __init__(self):
        self.children = {}        # char -> TrieNode
        self.is_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_word = True

    def _walk(self, prefix):
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node

    def search(self, word):
        node = self._walk(word)
        return node is not None and node.is_word

    def starts_with(self, prefix):
        return self._walk(prefix) is not None

is_word is what separates a stored word from a mere prefix. A trie holding "apple" answers search("app") as False but starts_with("app") as True.

Array-Backed Version

For fixed lowercase alphabets an array child list is faster and allocation-light.

class ArrayTrie:
    def __init__(self):
        self.children = [None] * 26
        self.is_word = False
        self.count = 0            # words passing through, for prefix counts

    def insert(self, word):
        node = self
        for ch in word:
            i = ord(ch) - 97
            if node.children[i] is None:
                node.children[i] = ArrayTrie()
            node = node.children[i]
            node.count += 1
        node.is_word = True

    def count_prefix(self, prefix):
        node = self
        for ch in prefix:
            i = ord(ch) - 97
            if node.children[i] is None:
                return 0
            node = node.children[i]
        return node.count

class TrieNode {
    TrieNode[] next = new TrieNode[26];
    boolean isWord;
}

class Trie {
    private final TrieNode root = new TrieNode();

    public void insert(String w) {
        TrieNode cur = root;
        for (char c : w.toCharArray()) {
            int i = c - 'a';
            if (cur.next[i] == null) cur.next[i] = new TrieNode();
            cur = cur.next[i];
        }
        cur.isWord = true;
    }

    public boolean search(String w) {
        TrieNode n = walk(w);
        return n != null && n.isWord;
    }

    public boolean startsWith(String p) { return walk(p) != null; }

    private TrieNode walk(String s) {
        TrieNode cur = root;
        for (char c : s.toCharArray()) {
            cur = cur.next[c - 'a'];
            if (cur == null) return null;
        }
        return cur;
    }
}

Deletion And Enumeration

def delete(self, word):
    """Unset is_word, then prune nodes that became useless."""
    path = [self.root]
    node = self.root
    for ch in word:
        if ch not in node.children:
            return False
        node = node.children[ch]
        path.append(node)
    if not node.is_word:
        return False
    node.is_word = False
    for i in range(len(path) - 1, 0, -1):
        cur, parent = path[i], path[i - 1]
        if cur.children or cur.is_word:
            break                      # still needed by another word
        del parent.children[word[i - 1]]
    return True

def words_with_prefix(self, prefix):
    """All stored words starting with prefix. O(m + output)."""
    node = self._walk(prefix)
    out = []
    if node is None:
        return out
    def dfs(n, path):
        if n.is_word:
            out.append(prefix + "".join(path))
        for ch, child in n.children.items():
            path.append(ch)
            dfs(child, path)
            path.pop()
    dfs(node, [])
    return out

def longest_common_prefix(words):
    """Walk down while there is exactly one child and no word ends."""
    t = Trie()
    for w in words:
        t.insert(w)
    node, out = t.root, []
    while len(node.children) == 1 and not node.is_word:
        ch, node = next(iter(node.children.items()))
        out.append(ch)
    return "".join(out)

Pruning on delete matters when the trie is long-lived. Without it, deleted words leave dead branches that keep answering starts_with correctly but waste memory forever.

Wildcard And Grid Search

class WordDictionary:
    """Supports '.' matching any single character."""
    def __init__(self):
        self.root = TrieNode()

    def add(self, word):
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_word = True

    def search(self, pattern):
        def go(node, i):
            if i == len(pattern):
                return node.is_word
            ch = pattern[i]
            if ch == ".":
                return any(go(c, i + 1) for c in node.children.values())
            child = node.children.get(ch)
            return child is not None and go(child, i + 1)
        return go(self.root, 0)


def find_words_in_grid(board, words):
    """Word Search II. Build a trie of the dictionary, one DFS per cell.
    The trie prunes as soon as the path is not any word's prefix."""
    root = TrieNode()
    for w in words:
        node = root
        for ch in w:
            node = node.children.setdefault(ch, TrieNode())
        node.is_word = True

    rows, cols = len(board), len(board[0])
    found = []

    def dfs(r, c, node, path):
        ch = board[r][c]
        nxt = node.children.get(ch)
        if nxt is None:
            return
        path.append(ch)
        if nxt.is_word:
            found.append("".join(path))
            nxt.is_word = False           # dedupe without a set
        board[r][c] = "#"                 # mark visited
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] != "#":
                dfs(nr, nc, nxt, path)
        board[r][c] = ch                  # restore
        path.pop()

    for r in range(rows):
        for c in range(cols):
            dfs(r, c, root, [])
    return found

Turning off is_word after a hit is the idiomatic dedupe here, and it also shrinks the remaining search.

Binary Trie For Maximum XOR

Store the bits of each number, most significant first. To maximize XOR, greedily walk toward the opposite bit at every level.

def find_maximum_xor(nums, bits=32):
    """Maximum a ^ b over all pairs. O(n * bits) instead of O(n^2)."""
    root = {}
    for x in nums:                        # insert
        node = root
        for i in range(bits - 1, -1, -1):
            b = (x >> i) & 1
            node = node.setdefault(b, {})

    best = 0
    for x in nums:                        # query
        node, cur = root, 0
        for i in range(bits - 1, -1, -1):
            b = (x >> i) & 1
            want = 1 - b                  # opposite bit gives a 1 in the XOR
            if want in node:
                cur |= 1 << i
                node = node[want]
            else:
                node = node[b]
        best = max(best, cur)
    return best

Gotchas

is_word is not optional. Without it a trie cannot distinguish a stored word from a prefix of one.
Alphabet assumptions. ord(ch) - 97 breaks on uppercase, digits, or Unicode. Use a dict when the alphabet is not known and small.
Space blowup. A 26-array per node costs about 26 pointers even for a single-child node. Prefer dicts for sparse data, and add __slots__ in Python.
Deletion without pruning leaks. The word stops matching but the nodes stay.
Wildcard search is exponential in the number of dots. Each . branches over every child, so "...." on a dense trie is expensive.
Restore mutated state. Grid DFS must put the original character back after recursing, and path.pop() must run on every exit path.
A trie is not always the answer. For exact-match-only lookups a hash set is simpler and faster. For a small fixed dictionary, sorting plus binary search on prefixes also works.
Recursion depth equals word length, which is fine for words but a problem for a binary trie over 64-bit keys built recursively. Iterate instead.