Chapter 16: Trie & Advanced Data Structures

16.1

Trie Fundamentals

A Trie (prefix tree) is a tree-based data structure optimized for string search and prefix matching. Each node represents a character, enabling O(m) search where m is the word length, independent of dictionary size.

What is a Trie?

A Trie stores strings in a tree where:

Root is empty, children are letters a-z
Each path from root to node spells a prefix
Leaf (or marked) nodes indicate word endings
Search, insert, delete all operate in O(m) time
Space: O(N*M) where N=words, M=avg length

TrieNode Structure

C#

public class TrieNode
{
    public Dictionary<char, TrieNode> children = new();
    public bool isWord = false;
    public int count = 0;  // For frequency tracking
}

ℹ️ Trie vs Hash Table: Tries excel at prefix queries and autocomplete; hash tables excel at exact matches. Tries use more space but provide ordered iteration.

16.2

Trie Operations

Insert Operation

C#

public void Insert(string word)
{
    TrieNode node = root;
    foreach (char c in word)
    {
        if (!node.children.ContainsKey(c))
            node.children[c] = new TrieNode();
        node = node.children[c];
    }
    node.isWord = true;
    node.count++;
}

Time: O(m) where m = word length | Space: O(1) amortized

Search Operation

C#

public bool Search(string word)
{
    TrieNode node = root;
    foreach (char c in word)
    {
        if (!node.children.ContainsKey(c))
            return false;
        node = node.children[c];
    }
    return node.isWord;
}

Time: O(m) | Space: O(1)

StartsWith Prefix Check

C#

public bool StartsWith(string prefix)
{
    TrieNode node = root;
    foreach (char c in prefix)
    {
        if (!node.children.ContainsKey(c))
            return false;
        node = node.children[c];
    }
    return true;
}

Time: O(m) | Space: O(1)

Delete Operation

C#

public bool Delete(string word)
{
    return DeleteHelper(root, word, 0);
}

private bool DeleteHelper(TrieNode node, string word, int idx)
{
    if (idx == word.Length)
    {
        if (!node.isWord) return false;
        node.isWord = false;
        return node.children.Count == 0;
    }

    char c = word[idx];
    if (!node.children.ContainsKey(c))
        return false;

    TrieNode child = node.children[c];
    bool shouldDeleteChild = DeleteHelper(child, word, idx + 1);

    if (shouldDeleteChild)
        node.children.Remove(c);

    return !node.isWord && node.children.Count == 0;
}

Time: O(m) | Space: O(m) recursive depth

16.3

Complete Trie Implementation

Full Trie class with all operations, supporting word insertion, exact search, prefix matching, deletion, and autocomplete.

C#

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

    public void Insert(string word)
    {
        TrieNode node = root;
        foreach (char c in word)
        {
            if (!node.children.ContainsKey(c))
                node.children[c] = new TrieNode();
            node = node.children[c];
        }
        node.isWord = true;
    }

    public bool Search(string word)
    {
        TrieNode node = FindNode(word);
        return node != null && node.isWord;
    }

    public bool StartsWith(string prefix)
    {
        return FindNode(prefix) != null;
    }

    private TrieNode FindNode(string s)
    {
        TrieNode node = root;
        foreach (char c in s)
        {
            if (!node.children.ContainsKey(c))
                return null;
            node = node.children[c];
        }
        return node;
    }

    public List<string> GetWordsWithPrefix(string prefix)
    {
        List<string> result = new();
        TrieNode node = FindNode(prefix);
        if (node == null) return result;

        DFS(node, prefix, result);
        return result;
    }

    private void DFS(TrieNode node, string path, List<string> result)
    {
        if (node.isWord)
            result.Add(path);
        foreach (var (c, child) in node.children)
            DFS(child, path + c, result);
    }

    public bool Delete(string word)
    {
        return DeleteHelper(root, word, 0);
    }

    private bool DeleteHelper(TrieNode node, string word, int idx)
    {
        if (idx == word.Length)
        {
            if (!node.isWord) return false;
            node.isWord = false;
            return node.children.Count == 0;
        }

        char c = word[idx];
        if (!node.children.ContainsKey(c))
            return false;

        TrieNode child = node.children[c];
        bool shouldDelete = DeleteHelper(child, word, idx + 1);

        if (shouldDelete)
            node.children.Remove(c);

        return !node.isWord && node.children.Count == 0;
    }
}

16.4

Trie Problems

LC 208: Implement Trie (Prefix Tree)

Design and implement a trie with insert, search, and startsWith methods.

String Design Easy

1

Time

O(m) per operation

Space

O(N*M)

C#

public class Trie
{
    private TrieNode root;

    public Trie() { root = new TrieNode(); }

    public void Insert(string word)
    {
        TrieNode node = root;
        foreach (char c in word)
        {
            if (!node.children.ContainsKey(c))
                node.children[c] = new TrieNode();
            node = node.children[c];
        }
        node.isWord = true;
    }

    public bool Search(string word)
    {
        TrieNode node = root;
        foreach (char c in word)
        {
            if (!node.children.ContainsKey(c))
                return false;
            node = node.children[c];
        }
        return node.isWord;
    }

    public bool StartsWith(string prefix)
    {
        TrieNode node = root;
        foreach (char c in prefix)
        {
            if (!node.children.ContainsKey(c))
                return false;
            node = node.children[c];
        }
        return true;
    }
}

LC 212: Word Search II

Find all words from a dictionary that exist in an m×n board. Words can be constructed by sequentially adjacent cells (horizontally or vertically).

String Backtracking Hard

2

Time

O(m*n*4^L)

Space

O(W*L)

C#

public IList<string> FindWords(char[][] board, string[] words)
{
    HashSet<string> result = new();
    TrieNode root = new TrieNode();

    foreach (var word in words)
    {
        TrieNode node = root;
        foreach (char c in word)
        {
            if (!node.children.ContainsKey(c))
                node.children[c] = new TrieNode();
            node = node.children[c];
        }
        node.isWord = true;
    }

    int rows = board.Length, cols = board[0].Length;
    bool[][] visited = new bool[rows][];

    for (int i = 0; i < rows; i++)
    {
        visited[i] = new bool[cols];
        for (int j = 0; j < cols; j++)
        {
            DFS(board, visited, i, j, root, "", result);
        }
    }

    return new List<string>(result);
}

private void DFS(char[][] board, bool[][] visited, int i, int j,
    TrieNode node, string path, HashSet<string> result)
{
    if (i < 0 || i >= board.Length || j < 0 || j >= board[0].Length ||
        visited[i][j])
        return;

    char c = board[i][j];
    if (!node.children.ContainsKey(c))
        return;

    visited[i][j] = true;
    node = node.children[c];

    if (node.isWord)
        result.Add(path + c);

    DFS(board, visited, i + 1, j, node, path + c, result);
    DFS(board, visited, i - 1, j, node, path + c, result);
    DFS(board, visited, i, j + 1, node, path + c, result);
    DFS(board, visited, i, j - 1, node, path + c, result);

    visited[i][j] = false;
}

LC 211: Add and Search Word

Design a data structure that supports adding words and searching for words with '.' as wildcard matching any single letter.

String Design Medium

3

Time

Search: O(N*26^m)

Space

O(N*M)

C#

public class WordDictionary
{
    private TrieNode root = new TrieNode();

    public void AddWord(string word)
    {
        TrieNode node = root;
        foreach (char c in word)
        {
            if (!node.children.ContainsKey(c))
                node.children[c] = new TrieNode();
            node = node.children[c];
        }
        node.isWord = true;
    }

    public bool Search(string word)
    {
        return SearchDFS(root, word, 0);
    }

    private bool SearchDFS(TrieNode node, string word, int idx)
    {
        if (idx == word.Length)
            return node.isWord;

        char c = word[idx];
        if (c == '.')
        {
            foreach (var child in node.children.Values)
                if (SearchDFS(child, word, idx + 1))
                    return true;
        }
        else
        {
            if (!node.children.ContainsKey(c))
                return false;
            return SearchDFS(node.children[c], word, idx + 1);
        }
        return false;
    }
}

LC 648: Replace Words

Replace words in a sentence with their shortest dictionary root if the root exists.

String Trie Medium

4

Time

O(N*M)

Space

O(D)

C#

public string ReplaceWords(IList<string> dictionary, string sentence)
{
    TrieNode root = new TrieNode();

    foreach (var word in dictionary)
    {
        TrieNode node = root;
        foreach (char c in word)
        {
            if (!node.children.ContainsKey(c))
                node.children[c] = new TrieNode();
            node = node.children[c];
        }
        node.isWord = true;
    }

    string[] words = sentence.Split(' ');
    StringBuilder result = new();

    foreach (var word in words)
    {
        TrieNode node = root;
        string root_word = "";

        foreach (char c in word)
        {
            if (!node.children.ContainsKey(c) || node.isWord)
                break;
            root_word += c;
            node = node.children[c];
        }

        if (node.isWord)
            result.Append(root_word);
        else
            result.Append(word);
        result.Append(' ');
    }

    return result.ToString().TrimEnd();
}

LC 720: Longest Word in Dictionary

Find the longest word in a dictionary that can be built by iteratively adding one letter at a time, starting from a single letter word.

String Trie Medium

5

Time

O(N*M*log N)

Space

O(N)

C#

public string LongestWord(string[] words)
{
    TrieNode root = new TrieNode();

    foreach (var word in words)
    {
        TrieNode node = root;
        foreach (char c in word)
        {
            if (!node.children.ContainsKey(c))
                node.children[c] = new TrieNode();
            node = node.children[c];
        }
        node.isWord = true;
    }

    Array.Sort(words, (a, b) =>
        b.Length != a.Length ? b.Length.CompareTo(a.Length) : a.CompareTo(b));

    foreach (var word in words)
    {
        TrieNode node = root;
        bool valid = true;

        foreach (char c in word)
        {
            node = node.children[c];
            if (!node.isWord)
            {
                valid = false;
                break;
            }
        }

        if (valid)
            return word;
    }

    return "";
}

16.5

Segment Trees

A Segment Tree is a binary tree where each node stores an aggregate function (sum, min, max) over a range. Enables O(log n) range queries and O(log n) point updates.

Segment Tree Concepts

Structure: Binary tree with n leaves (array elements)
Build: O(n) - bottom-up construction
Query: O(log n) - find aggregate over range [L, R]
Update: O(log n) - modify single element
Space: O(4n) - array-based implementation

Segment Tree Implementation (100+ lines)

C#

public class SegmentTree
{
    private int[] tree;
    private int n;

    public SegmentTree(int[] nums)
    {
        n = nums.Length;
        tree = new int[4 * n];
        if (n > 0)
            Build(nums, 0, 0, n - 1);
    }

    private void Build(int[] nums, int node, int start, int end)
    {
        if (start == end)
        {
            tree[node] = nums[start];
        }
        else
        {
            int mid = start + (end - start) / 2;
            Build(nums, 2 * node + 1, start, mid);
            Build(nums, 2 * node + 2, mid + 1, end);
            tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
        }
    }

    public void Update(int index, int val)
    {
        UpdateHelper(0, 0, n - 1, index, val);
    }

    private void UpdateHelper(int node, int start, int end, int idx, int val)
    {
        if (start == end)
        {
            tree[node] = val;
        }
        else
        {
            int mid = start + (end - start) / 2;
            if (idx <= mid)
                UpdateHelper(2 * node + 1, start, mid, idx, val);
            else
                UpdateHelper(2 * node + 2, mid + 1, end, idx, val);
            tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
        }
    }

    public int QuerySum(int left, int right)
    {
        return QueryHelper(0, 0, n - 1, left, right);
    }

    private int QueryHelper(int node, int start, int end, int L, int R)
    {
        if (R < start || end < L)
            return 0;

        if (L <= start && end <= R)
            return tree[node];

        int mid = start + (end - start) / 2;
        int p1 = QueryHelper(2 * node + 1, start, mid, L, R);
        int p2 = QueryHelper(2 * node + 2, mid + 1, end, L, R);
        return p1 + p2;
    }

    // Query minimum in range
    public int QueryMin(int left, int right)
    {
        return QueryMinHelper(0, 0, n - 1, left, right);
    }

    private int QueryMinHelper(int node, int start, int end, int L, int R)
    {
        if (R < start || end < L)
            return int.MaxValue;

        if (L <= start && end <= R)
            return tree[node];

        int mid = start + (end - start) / 2;
        int p1 = QueryMinHelper(2 * node + 1, start, mid, L, R);
        int p2 = QueryMinHelper(2 * node + 2, mid + 1, end, L, R);
        return Math.Min(p1, p2);
    }
}

LC 307: Range Sum Query - Mutable

Implement a class for range sum queries with element updates using segment tree.

SegmentTree RangeQuery Medium

6

Time

O(log n)

Space

O(4n)

C#

public class NumArray
{
    private SegmentTree st;

    public NumArray(int[] nums)
    {
        st = new SegmentTree(nums);
    }

    public void Update(int index, int val)
    {
        st.Update(index, val);
    }

    public int SumRange(int left, int right)
    {
        return st.QuerySum(left, right);
    }
}

16.6

Fenwick Tree (Binary Indexed Tree)

A Fenwick Tree is a space-efficient data structure for prefix sum queries and point updates in O(log n) time, using only O(n) space.

Fenwick Tree Implementation

C#

public class FenwickTree
{
    private int[] tree;
    private int n;

    public FenwickTree(int size)
    {
        n = size;
        tree = new int[n + 1];
    }

    // Point update: add delta to index
    public void Update(int index, int delta)
    {
        index++;  // 1-indexed
        while (index <= n)
        {
            tree[index] += delta;
            index += index & (-index);  // Add lowest set bit
        }
    }

    // Prefix sum query [0, index]
    public int Query(int index)
    {
        index++;  // 1-indexed
        int sum = 0;
        while (index > 0)
        {
            sum += tree[index];
            index -= index & (-index);
        }
        return sum;
    }

    // Range sum [left, right]
    public int RangeQuery(int left, int right)
    {
        if (left == 0)
            return Query(right);
        return Query(right) - Query(left - 1);
    }

    // Build from array in O(n log n)
    public static FenwickTree Build(int[] nums)
    {
        FenwickTree ft = new FenwickTree(nums.Length);
        for (int i = 0; i < nums.Length; i++)
            ft.Update(i, nums[i]);
        return ft;
    }
}

ℹ️ Key Insight: index & (-index) isolates the lowest set bit. This enables O(log n) navigation of the tree structure without explicit pointers.

16.7

Segment Tree vs Fenwick Tree

Feature	Segment Tree	Fenwick Tree
Query Time	O(log n)	O(log n)
Update Time	O(log n)	O(log n)
Space	O(4n)	O(n)
Build Time	O(n)	O(n log n)
Range Min/Max	Yes	No (sum only)
Range Update	With lazy prop	No
Implementation	Recursive	Iterative
Use When	Multiple functions, complex queries	Sum queries, space-efficient

✓ Interview Tip: Use Fenwick Tree for sum queries to impress with space efficiency. Use Segment Tree when you need min/max or range updates.

16.8

Union-Find (Disjoint Set Union)

Union-Find efficiently manages a collection of disjoint sets with two operations: Find (with path compression) and Union (with rank optimization). Both approach O(1) amortized time.

Complete Union-Find Class

C#

public class UnionFind
{
    private int[] parent;
    private int[] rank;
    private int count;

    public UnionFind(int n)
    {
        parent = new int[n];
        rank = new int[n];
        count = n;
        for (int i = 0; i < n; i++)
            parent[i] = i;
    }

    // Find with path compression
    public int Find(int x)
    {
        if (parent[x] != x)
            parent[x] = Find(parent[x]);  // Path compression
        return parent[x];
    }

    // Union by rank
    public bool Union(int x, int y)
    {
        int rootX = Find(x);
        int rootY = Find(y);

        if (rootX == rootY)
            return false;  // Already connected

        if (rank[rootX] < rank[rootY])
            parent[rootX] = rootY;
        else if (rank[rootX] > rank[rootY])
            parent[rootY] = rootX;
        else
        {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
        count--;
        return true;  // Successfully merged
    }

    // Check if two elements are in same set
    public bool Connected(int x, int y)
    {
        return Find(x) == Find(y);
    }

    // Number of connected components
    public int GetCount()
    {
        return count;
    }
}

⚠ Path Compression: Every find operation updates parent pointers to point directly to root, flattening the tree structure. Combined with union by rank, achieves near-O(1) amortized time.

16.9

Union-Find Problems

LC 323: Number of Connected Components in an Undirected Graph

Find the number of connected components in an undirected graph.

UnionFind Graph Medium

7

Time

O(n*α(n))

Space

O(n)

C#

public int CountComponents(int n, int[][] edges)
{
    UnionFind uf = new UnionFind(n);

    foreach (var edge in edges)
        uf.Union(edge[0], edge[1]);

    return uf.GetCount();
}

LC 684: Redundant Connection

Find an edge that creates a cycle in an undirected tree (n nodes, n edges). Return any redundant edge.

UnionFind Graph Medium

8

Time

O(n*α(n))

Space

O(n)

C#

public int[] FindRedundantConnection(int[][] edges)
{
    UnionFind uf = new UnionFind(edges.Length + 1);

    foreach (var edge in edges)
    {
        if (!uf.Union(edge[0], edge[1]))
            return edge;  // Found cycle
    }

    return new int[] { };
}

LC 721: Accounts Merge

Merge accounts with shared email addresses. Return accounts with all merged emails in sorted order.

UnionFind String Hard

9

Time

O(n*k*α(n))

Space

O(n*k)

C#

public IList<IList<string>> AccountsMerge(IList<IList<string>> accounts)
{
    Dictionary<string, int> emailToId = new();
    Dictionary<int, List<string>> idToEmails = new();
    UnionFind uf = new UnionFind(accounts.Count);

    int idx = 0;
    foreach (var account in accounts)
    {
        List<string> emails = new(account);
        string name = emails[0];
        emails.RemoveAt(0);

        int firstEmailId = -1;
        foreach (var email in emails)
        {
            if (!emailToId.ContainsKey(email))
            {
                emailToId[email] = idx;
                firstEmailId = idx;
            }
            else
            {
                firstEmailId = emailToId[email];
            }
            uf.Union(idx, firstEmailId);
        }
        idx++;
    }

    foreach (var (email, accountId) in emailToId)
    {
        int root = uf.Find(accountId);
        if (!idToEmails.ContainsKey(root))
            idToEmails[root] = new List<string>();
        idToEmails[root].Add(email);
    }

    IList<IList<string>> result = new List<IList<string>>();
    idx = 0;
    foreach (var account in accounts)
    {
        int root = uf.Find(idx);
        if (idToEmails.ContainsKey(root))
        {
            List<string> merged = new();
            merged.Add(account[0]);
            idToEmails[root].Sort();
            merged.AddRange(idToEmails[root]);
            result.Add(merged);
            idToEmails.Remove(root);
        }
        idx++;
    }

    return result;
}

LC 547: Number of Provinces

Find the number of provinces given an isConnected matrix (0=not connected, 1=connected).

UnionFind Graph Medium

10

Time

O(n²*α(n))

Space

O(n)

C#

public int FindCircleNum(int[][] isConnected)
{
    int n = isConnected.Length;
    UnionFind uf = new UnionFind(n);

    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            if (isConnected[i][j] == 1)
                uf.Union(i, j);
        }
    }

    return uf.GetCount();
}

16.10

Skip Lists

A Skip List is a probabilistic data structure that maintains sorted sequences with O(log n) search, insertion, and deletion in expectation. Alternative to balanced trees.

Skip List Concepts

Structure: Multiple levels of sorted linked lists; higher levels act as "express lanes"
Height Assignment: Probabilistic - flip coin to decide if node belongs to next level
Search: O(log n) expected - start at highest level, descend when overshooting
Insert/Delete: O(log n) expected - find position, update pointers
Space: O(n) expected - average node has 1 + 1/p pointers
Advantage: Simpler than AVL/Red-Black trees; probabilistic guarantees

ℹ️ Practical Use: Skip Lists are used in Redis, LevelDB, and ConcurrentSkipListMap in Java. Good for distributed systems where rebalancing is expensive.

16.11

LRU & LFU Caches

LRU Cache - Least Recently Used (LC 146)

Design a cache that evicts the least recently used item when capacity is exceeded. O(1) get and put operations using HashMap + Doubly Linked List.

C#

public class LRUCache
{
    private class Node
    {
        public int key, val;
        public Node prev, next;
        public Node(int k, int v) { key = k; val = v; }
    }

    private int capacity;
    private Dictionary<int, Node> cache = new();
    private Node head = new Node(0, 0);
    private Node tail = new Node(0, 0);

    public LRUCache(int capacity)
    {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    public int Get(int key)
    {
        if (!cache.ContainsKey(key))
            return -1;

        Node node = cache[key];
        MoveToHead(node);
        return node.val;
    }

    public void Put(int key, int value)
    {
        if (cache.ContainsKey(key))
        {
            Node node = cache[key];
            node.val = value;
            MoveToHead(node);
        }
        else
        {
            Node newNode = new Node(key, value);
            cache[key] = newNode;
            AddToHead(newNode);

            if (cache.Count > capacity)
            {
                Node oldest = tail.prev;
                RemoveNode(oldest);
                cache.Remove(oldest.key);
            }
        }
    }

    private void AddToHead(Node node)
    {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }

    private void RemoveNode(Node node)
    {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void MoveToHead(Node node)
    {
        RemoveNode(node);
        AddToHead(node);
    }
}

Get Time

O(1)

Put Time

O(1)

Space

O(capacity)

LFU Cache - Least Frequently Used (LC 460)

Evicts the item with the lowest frequency. If tied, evict the least recently used among those with the lowest frequency.

✓ LFU Implementation: Requires three layers: HashMap(key→Node), HashMap(freq→list of nodes), HashMap(node→freq). When incrementing frequency, move node to next frequency list.

16.12

Bloom Filters

A Bloom Filter is a space-efficient probabilistic data structure for membership testing. Uses multiple hash functions and bit array with O(1) insert and lookup, but allows false positives.

Bloom Filter Concepts

Structure: Bit array of size m, k independent hash functions
Insert: Hash element k times, set those k bit positions to 1. O(k) = O(1)
Lookup: Hash element k times, check if all k positions are 1. O(k) = O(1)
False Positives: Possible (element not added but all bits set). Tunable with m and k.
False Negatives: Never (if element was added, bits are definitely set)
Space: O(m bits) - much smaller than hash table for same set

Simple Bloom Filter Implementation

C#

public class BloomFilter
{
    private BitArray bits;
    private int k;  // number of hash functions

    public BloomFilter(int size, int hashFunctions)
    {
        bits = new BitArray(size, false);
        k = hashFunctions;
    }

    public void Add(string element)
    {
        for (int i = 0; i < k; i++)
        {
            int hash = Hash(element, i) % bits.Length;
            bits[hash] = true;
        }
    }

    public bool MightContain(string element)
    {
        for (int i = 0; i < k; i++)
        {
            int hash = Hash(element, i) % bits.Length;
            if (!bits[hash])
                return false;  // Definitely not present
        }
        return true;  // Probably present
    }

    private int Hash(string s, int seed)
    {
        int hash = seed;
        foreach (char c in s)
            hash = hash * 31 + c;
        return Math.Abs(hash);
    }
}

⚠ Use Cases: Web crawlers (visited URLs), distributed caches (CDN existence checks), spell checkers, duplicate detection. NOT suitable when false positives are unacceptable.

16.13

Interview Tips & When to Use Each DS

Trie

Use When:

— Autocomplete/prefix search — Spell checking — IP routing — Dictionary problems — Word search with board

Segment Tree

Use When:

— Range min/max/sum queries — Complex range updates — Lazy propagation needed — Multiple aggregate functions

Fenwick Tree

Use When:

— Sum queries & updates only — Need space efficiency (O(n)) — Cleaner/simpler code preferred — Competitive programming

Union-Find

Use When:

— Connected components — Cycle detection in graph — Merge disjoint sets — Kruskal's algorithm

Skip List

Use When:

— Ordered data needed — Simpler than AVL/Red-Black — Distributed systems — Probabilistic OK

LRU Cache

Use When:

— Temporal locality matters — Fixed capacity eviction — Database/page caching — Most recently used = best

Interview Strategy

Before Coding

1. Understand problem constraints (n, memory, operations) 2. Identify key pattern (string search, range query, connectivity) 3. State time/space tradeoff clearly 4. Mention pros/cons vs alternatives 5. Check edge cases (empty, single element, capacity)

While Coding

1. Write clear variable names 2. Add comments for complex logic 3. Test immediately with examples 4. Handle boundary conditions 5. Optimize iteratively, don't prematurely optimize

Common Mistakes to Avoid

✗ Trie: Forgetting to mark end of word OR not handling wildcard searches

✗ Segment Tree: Off-by-one errors in range boundaries, forgetting to update parent nodes

✗ Union-Find: Skipping path compression OR union by rank, leading to O(n) operations

✗ LRU Cache: Not properly linking/unlinking nodes from doubly linked list on eviction

Performance Cheat Sheet

DS	Insert	Search	Delete	Space	Best For
Trie	O(m)	O(m)	O(m)	O(N*M)	Prefix search
SegTree	O(log n)	O(log n)	N/A	O(4n)	Range queries
FenwickTree	O(log n)	O(log n)	N/A	O(n)	Sum queries
UnionFind	O(α(n))	O(α(n))	O(α(n))	O(n)	Connectivity
SkipList	O(log n)	O(log n)	O(log n)	O(n)	Ordered data
LRUCache	O(1)	O(1)	O(1)	O(capacity)	Caching