Menu

Earn Premium with Referrals

Invite your friends and earn Premium rewards through our referral program.

See how it works and start inviting friends.

Trie Revision
DSA

Trie Revision

Quickly revise trie structure, insertion, searching, prefixes, and common applications.

Insert(word):
    node = root

    for each character c in word:
        if node does not have child c:
            create new node
        move to child c

    mark node as end of word

Core Idea

  • Each node = prefix state
  • Root = empty string
  • Path = word

Time: O(L) per word

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isEnd = false;
}

class Trie {
    TrieNode root = new TrieNode();

    public void insert(String word) {
        TrieNode node = root;

        for (char c : word.toCharArray()) {
            int idx = c - 'a';

            if (node.children[idx] == null)
                node.children[idx] = new TrieNode();

            node = node.children[idx];
        }

        node.isEnd = true;
    }
}
class TrieNode:
    def __init__(self):
        self.children = {}
        self.isEnd = False


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

    def insert(self, word):
        node = self.root

        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()

            node = node.children[c]

        node.isEnd = True
struct TrieNode {
    TrieNode* children[26]{};
    bool isEnd = false;
};

struct Trie {
    TrieNode* root = new TrieNode();

    void insert(const string& word) {
        TrieNode* node = root;

        for (char c : word) {
            int idx = c - 'a';

            if (!node->children[idx])
                node->children[idx] = new TrieNode();

            node = node->children[idx];
        }

        node->isEnd = true;
    }
};
class TrieNode {
    constructor() {
        this.children = {};
        this.isEnd = false;
    }
}

class Trie {
    constructor() {
        this.root = new TrieNode();
    }

    insert(word) {
        let node = this.root;

        for (const c of word) {
            if (!(c in node.children))
                node.children[c] = new TrieNode();

            node = node.children[c];
        }

        node.isEnd = true;
    }
}

2 Trie Search (Exact Word Match)

Search(word):
    node = root

    for each character c:
        if child c does not exist:
            return false
        move to child

    return node.isEnd

Use Cases

  • Dictionary lookup
  • Word validation
public boolean search(String word) {
    TrieNode node = root;

    for (char c : word.toCharArray()) {
        int idx = c - 'a';

        if (node.children[idx] == null)
            return false;

        node = node.children[idx];
    }

    return node.isEnd;
}
def search(self, word):
    node = self.root

    for c in word:
        if c not in node.children:
            return False

        node = node.children[c]

    return node.isEnd
bool search(const string& word) {
    TrieNode* node = root;

    for (char c : word) {
        int idx = c - 'a';

        if (!node->children[idx])
            return false;

        node = node->children[idx];
    }

    return node->isEnd;
}
search(word) {
    let node = this.root;

    for (const c of word) {
        if (!(c in node.children))
            return false;

        node = node.children[c];
    }

    return node.isEnd;
}

3 Prefix Search (Starts With)

StartsWith(prefix):
    node = root

    for each character c in prefix:
        if child c does not exist:
            return false
        move to child

    return true

Use Cases

  • Autocomplete
  • Dictionary suggestions
  • Search optimization
public boolean startsWith(String prefix) {
    TrieNode node = root;

    for (char c : prefix.toCharArray()) {
        int idx = c - 'a';

        if (node.children[idx] == null)
            return false;

        node = node.children[idx];
    }

    return true;
}
def starts_with(self, prefix):
    node = self.root

    for c in prefix:
        if c not in node.children:
            return False

        node = node.children[c]

    return True
bool startsWith(const string& prefix) {
    TrieNode* node = root;

    for (char c : prefix) {
        int idx = c - 'a';

        if (!node->children[idx])
            return false;

        node = node->children[idx];
    }

    return true;
}
startsWith(prefix) {
    let node = this.root;

    for (const c of prefix) {
        if (!(c in node.children))
            return false;

        node = node.children[c];
    }

    return true;
}

4 Trie + DFS (Wildcard / Pattern Matching)

Search(word, node, index):

    if index == word.length:
        return node.isEnd

    char = word[index]

    if char != '.':
        go to child char
    else:
        try all children:
            if any returns true → return true

    return false

Keywords

  • wildcard ’.’
  • pattern match
  • dictionary search
public boolean searchWithWildcard(String word) {
    return dfs(root, word, 0);
}

private boolean dfs(TrieNode node, String word, int i) {
    if (node == null) return false;

    if (i == word.length())
        return node.isEnd;

    char c = word.charAt(i);

    if (c != '.') {
        return dfs(node.children[c - 'a'], word, i + 1);
    }

    for (TrieNode child : node.children) {
        if (child != null &&
            dfs(child, word, i + 1))
            return true;
    }

    return false;
}
def search_with_wildcard(self, word):
    return self.dfs(self.root, word, 0)

def dfs(self, node, word, i):
    if node is None:
        return False

    if i == len(word):
        return node.isEnd

    c = word[i]

    if c != '.':
        return self.dfs(node.children.get(c), word, i + 1)

    for child in node.children.values():
        if self.dfs(child, word, i + 1):
            return True

    return False
bool searchWithWildcard(const string& word) {
    return dfs(root, word, 0);
}

private:
bool dfs(TrieNode* node, const string& word, int i) {
    if (!node) return false;

    if (i == word.size())
        return node->isEnd;

    char c = word[i];

    if (c != '.') {
        return dfs(node->children[c - 'a'], word, i + 1);
    }

    for (TrieNode* child : node->children) {
        if (child &&
            dfs(child, word, i + 1))
            return true;
    }

    return false;
}
searchWithWildcard(word) {
    return this.dfs(this.root, word, 0);
}

dfs(node, word, i) {
    if (!node) return false;

    if (i === word.length)
        return node.isEnd;

    const c = word[i];

    if (c !== '.') {
        return this.dfs(node.children[c], word, i + 1);
    }

    for (const child of Object.values(node.children)) {
        if (this.dfs(child, word, i + 1))
            return true;
    }

    return false;
}

5 Trie + Word Break (DFS / DP Integration)

WordBreak(index):

    if index == n:
        return true

    node = root

    for i from index to n:
        if path exists in trie:
            if node.isEnd and WordBreak(i+1):
                return true

        else break

    return false

Use Cases

  • Sentence segmentation
  • Dictionary-based splitting
public boolean wordBreak(String s, Set<String> dict) {
    return dfs(s, 0, new Trie());
}

private boolean dfs(String s, int start, Trie trie) {
    if (start == s.length()) return true;

    TrieNode node = trie.root;

    for (int i = start; i < s.length(); i++) {
        int idx = s.charAt(i) - 'a';

        if (node.children[idx] == null)
            return false;

        node = node.children[idx];

        if (node.isEnd &&
            dfs(s, i + 1, trie))
            return true;
    }

    return false;
}
def word_break(self, s, word_set):
    return self._dfs(s, 0)

def _dfs(self, s, start):
    if start == len(s):
        return True

    node = self.root

    for i in range(start, len(s)):
        c = s[i]

        if c not in node.children:
            return False

        node = node.children[c]

        if node.isEnd and self._dfs(s, i + 1):
            return True

    return False
bool wordBreak(const string& s, unordered_set<string>& dict) {
    return dfs(s, 0);
}

private:
bool dfs(const string& s, int start) {
    if (start == s.size()) return true;

    TrieNode* node = root;

    for (int i = start; i < s.size(); i++) {
        int idx = s[i] - 'a';

        if (!node->children[idx])
            return false;

        node = node->children[idx];

        if (node->isEnd &&
            dfs(s, i + 1))
            return true;
    }

    return false;
}
wordBreak(s, dict) {
    return this.dfs(s, 0);
}

dfs(s, start) {
    if (start === s.length) return true;

    let node = this.root;

    for (let i = start; i < s.length; i++) {
        const c = s[i];

        if (!(c in node.children))
            return false;

        node = node.children[c];

        if (node.isEnd && this.dfs(s, i + 1))
            return true;
    }

    return false;
}

6 Trie for Multiple Words (Dictionary Builder)

For each word:
    insert into trie

Then use search/prefix operations

Use Cases

  • Word dictionary
  • Search suggestions system
class Trie {
    TrieNode root = new TrieNode();

    public void build(String[] words) {
        for (String w : words)
            insert(w);
    }

    private void insert(String word) {
        TrieNode node = root;

        for (char c : word.toCharArray()) {
            int idx = c - 'a';

            if (node.children[idx] == null)
                node.children[idx] = new TrieNode();

            node = node.children[idx];
        }
        node.isEnd = true;
    }
}
class Trie:
    def __init__(self):
        self.root = TrieNode()

    def build(self, words):
        for w in words:
            self.insert(w)

    def insert(self, word):
        node = self.root

        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()

            node = node.children[c]
        node.isEnd = True
struct Trie {
    TrieNode* root = new TrieNode();

    void build(const vector<string>& words) {
        for (const string& w : words)
            insert(w);
    }

    void insert(const string& word) {
        TrieNode* node = root;

        for (char c : word) {
            int idx = c - 'a';

            if (!node->children[idx])
                node->children[idx] = new TrieNode();

            node = node->children[idx];
        }
        node->isEnd = true;
    }
};
class Trie {
    constructor() {
        this.root = new TrieNode();
    }

    build(words) {
        for (const w of words)
            this.insert(w);
    }

    insert(word) {
        let node = this.root;

        for (const c of word) {
            if (!(c in node.children))
                node.children[c] = new TrieNode();

            node = node.children[c];
        }
        node.isEnd = true;
    }
}

7 Bitwise Trie (Bonus – XOR Problems)

Insert number in binary (31 bits)

For XOR query:
    try opposite bit first

Use Cases

  • Maximum XOR pair
  • Min XOR
  • Bit manipulation optimization
class BitTrieNode {
    BitTrieNode[] child = new BitTrieNode[2];
}

class BitTrie {
    BitTrieNode root = new BitTrieNode();

    public void insert(int num) {
        BitTrieNode node = root;

        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1;

            if (node.child[bit] == null)
                node.child[bit] = new BitTrieNode();

            node = node.child[bit];
        }
    }

    public int getMaxXor(int num) {
        BitTrieNode node = root;
        int ans = 0;

        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1;
            int opp = 1 - bit;

            if (node.child[opp] != null) {
                ans |= (1 << i);
                node = node.child[opp];
            } else {
                node = node.child[bit];
            }
        }

        return ans;
    }
}
class BitTrieNode:
    def __init__(self):
        self.child = [None, None]


class BitTrie:
    def __init__(self):
        self.root = BitTrieNode()

    def insert(self, num):
        node = self.root

        for i in range(31, -1, -1):
            bit = (num >> i) & 1

            if node.child[bit] is None:
                node.child[bit] = BitTrieNode()

            node = node.child[bit]

    def get_max_xor(self, num):
        node = self.root
        ans = 0

        for i in range(31, -1, -1):
            bit = (num >> i) & 1
            opp = 1 - bit

            if node.child[opp] is not None:
                ans |= (1 << i)
                node = node.child[opp]
            else:
                node = node.child[bit]

        return ans
struct BitTrieNode {
    BitTrieNode* child[2]{};
};

struct BitTrie {
    BitTrieNode* root = new BitTrieNode();

    void insert(int num) {
        BitTrieNode* node = root;

        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1;

            if (!node->child[bit])
                node->child[bit] = new BitTrieNode();

            node = node->child[bit];
        }
    }

    int getMaxXor(int num) {
        BitTrieNode* node = root;
        int ans = 0;

        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1;
            int opp = 1 - bit;

            if (node->child[opp]) {
                ans |= (1 << i);
                node = node->child[opp];
            } else {
                node = node->child[bit];
            }
        }

        return ans;
    }
};
class BitTrieNode {
    constructor() {
        this.child = [null, null];
    }
}

class BitTrie {
    constructor() {
        this.root = new BitTrieNode();
    }

    insert(num) {
        let node = this.root;

        for (let i = 31; i >= 0; i--) {
            const bit = (num >> i) & 1;

            if (!node.child[bit])
                node.child[bit] = new BitTrieNode();

            node = node.child[bit];
        }
    }

    getMaxXor(num) {
        let node = this.root;
        let ans = 0;

        for (let i = 31; i >= 0; i--) {
            const bit = (num >> i) & 1;
            const opp = 1 - bit;

            if (node.child[opp]) {
                ans |= (1 << i);
                node = node.child[opp];
            } else {
                node = node.child[bit];
            }
        }

        return ans;
    }
}

Trie Master Summary

### Core Idea
- Trie = prefix tree for strings
- Each node = partial prefix state

### When to Use
- Prefix search → YES
- Dictionary problems → YES
- Repeated string lookup → YES
- Pattern matching → YES
- XOR / bits → YES (bitwise trie)

### Recognition Triggers
- "starts with"
- "autocomplete"
- "dictionary search"
- "many words + queries"
- "fast lookup of strings"

### Mental Model
INSERT → TRAVERSE → PREFIX MATCH → DFS EXPLORE → OPTIMIZE

My Private Notes

Notes are auto-saved locally to this device.