Menu

Earn Premium with Referrals

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

See how it works and start inviting friends.

Basic Trie
DSA

Basic Trie

Learn how to implement a trie and efficiently insert, search, and check prefixes of strings.

A trie (prefix tree) stores strings character-by-character — shared prefixes share nodes.

Focus on recognizing:

“Prefix” / “autocomplete” / “dictionary of words” → trie

Pattern 1: Insert, Search, StartsWith

Watch cat, car and dog build a trie — shared prefix ca, then queries walk or fail. Press ▶ to animate.

Trie — Insert, Search & Prefix

Build a trie from a small word list and use it to test exact membership and prefixes.

Each word is inserted by walking or creating a child per character, so shared prefixes reuse nodes. Search walks the characters and requires the end-mark; startsWith succeeds as soon as the prefix path exists.

TRIE VISUALIZER
Steps –
Rcdaot★r★g★
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        insert(w): cur = root
                      
                        2
                          for ch in w:
                      
                        3
                            if ch not in cur.children: create node
                      
                        4
                            cur = cur.children[ch]
                      
                        5
                          cur.isEnd = true

One node class, three methods:

class Trie {
    private final Trie[] children = new Trie[26];
    private boolean isEnd;

    public void insert(String word) {
        Trie cur = this;
        for (char c : word.toCharArray()) {
            int i = c - 'a';
            if (cur.children[i] == null)
                cur.children[i] = new Trie();
            cur = cur.children[i];
        }
        cur.isEnd = true;
    }

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

    public boolean search(String word) {
        Trie node = walk(word);
        return node != null && node.isEnd;
    }

    public boolean startsWith(String prefix) {
        return walk(prefix) != null;
    }
}
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False


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

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

    def _walk(self, s):
        cur = self.root
        for ch in s:
            cur = cur.children.get(ch)
            if cur is None:
                return None
        return cur

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

    def starts_with(self, prefix):
        return self._walk(prefix) is not None
struct TrieNode {
    TrieNode* children[26] = {};
    bool isEnd = false;
};

class Trie {
    TrieNode root;

    TrieNode* walk(const string& s) {
        TrieNode* cur = &root;
        for (char c : s) {
            cur = cur->children[c - 'a'];
            if (!cur) return nullptr;
        }
        return cur;
    }

public:
    void insert(const string& word) {
        TrieNode* cur = &root;
        for (char c : word) {
            auto& next = cur->children[c - 'a'];
            if (!next) next = new TrieNode();
            cur = next;
        }
        cur->isEnd = true;
    }

    bool search(const string& word) {
        TrieNode* n = walk(word);
        return n && n->isEnd;
    }

    bool startsWith(const string& prefix) {
        return walk(prefix) != nullptr;
    }
};
class TrieNode {
  children = new Map();
  isEnd = false;
}

class Trie {
  root = new TrieNode();

  insert(word) {
    let cur = this.root;
    for (const ch of word) {
      if (!cur.children.has(ch))
        cur.children.set(ch, new TrieNode());
      cur = cur.children.get(ch);
    }
    cur.isEnd = true;
  }

  #walk(s) {
    let cur = this.root;
    for (const ch of s) {
      cur = cur.children.get(ch);
      if (!cur) return null;
    }
    return cur;
  }

  search(word) {
    const node = this.#walk(word);
    return node !== null && node.isEnd;
  }

  startsWith(prefix) {
    return this.#walk(prefix) !== null;
  }
}

search needs isEnd — "car" exists inside "card" but isn’t a stored word.

Insert creates missing nodes; query just walks. isEnd separates words from prefixes.

Pattern 2: Autocomplete (All Words With Prefix)

Walk the prefix once, then harvest every end-marked word below.

Trie Autocomplete

Given a prefix, return every word in the trie that begins with it.

Walk the prefix path; if it exists, DFS the subtree below it and emit every node marked as a word end.

TRIE VISUALIZER
Steps –
Rcd★at★r★p
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        node = walk(prefix)             // 'ca'
                      
                        2
                        if node == null → no matches
                      
                        3
                        DFS from node:
                      
                        4
                          at isEnd → emit word

DFS from the prefix’s end node:

public List<String> autocomplete(String prefix) {
    List<String> result = new ArrayList<>();
    TrieNode node = walkTo(root, prefix);

    if (node != null)
        dfs(node, new StringBuilder(prefix), result);

    return result;
}

private void dfs(TrieNode node, StringBuilder path,
                 List<String> out) {
    if (node.isEnd) out.add(path.toString());

    for (int i = 0; i < 26; i++) {
        if (node.children[i] != null) {
            path.append((char) ('a' + i));
            dfs(node.children[i], path, out);
            path.deleteCharAt(path.length() - 1);
        }
    }
}
def autocomplete(root, prefix):
    # walk to prefix end
    node = root
    for ch in prefix:
        node = node.children.get(ch)
        if node is None:
            return []

    result = []

    def dfs(cur, path):
        if cur.is_end:
            result.append("".join(path))
        for ch, child in cur.children.items():
            path.append(ch)
            dfs(child, path)
            path.pop()

    dfs(node, list(prefix))
    return result
void dfs(TrieNode* node, string& path, vector<string>& out) {
    if (node->isEnd) out.push_back(path);

    for (int i = 0; i < 26; i++) {
        if (node->children[i]) {
            path.push_back('a' + i);
            dfs(node->children[i], path, out);
            path.pop_back();
        }
    }
}

vector<string> autocomplete(TrieNode* root, const string& prefix) {
    TrieNode* node = root;
    for (char c : prefix) {
        node = node->children[c - 'a'];
        if (!node) return {};
    }

    vector<string> out;
    string path = prefix;
    dfs(node, path, out);
    return out;
}
function autocomplete(root, prefix) {
  let node = root;
  for (const ch of prefix) {
    node = node.children.get(ch);
    if (!node) return [];
  }

  const out = [];

  const dfs = (cur, path) => {
    if (cur.isEnd) out.push(path);
    for (const [ch, child] of cur.children)
      dfs(child, path + ch);
  };

  dfs(node, prefix);
  return out;
}

The prefix itself is the DFS starting path — everything below it shares that stem.

Common Mistakes

Forgetting isEnd in search.

startsWith("ca") succeeds even though "ca" was never inserted as a word.

Rebuilding the trie per query.

Build once at construction; queries are pure walks.

Using a HashMap when alphabet is fixed a–z.

Array-of-26 is faster and idiomatic in Java/C++; maps shine with unicode.

Complexity

OperationTimeSpace
insert / search / startsWithO(m) — word lengthO(total chars)
Autocomplete(prefix)O(P + matches·L)O(depth) recursion

My Private Notes

Notes are auto-saved locally to this device.