Advanced Trees

Trie (Prefix Tree)

What is a Trie (Prefix Tree)?

A Trie (pronounced "try", from re-"trie"-val, and also called a Prefix Tree) stores a set of strings by turning shared prefixes into shared paths through the tree. Unlike a BST, a trie doesn't store a whole key per node — each edge represents a single character, and the string you get by reading the characters from the root down to any node is that node's prefix. A small boolean flag on a node marks whether the prefix ending there is also a complete word that was inserted.

Why Use a Trie?

This "shared paths for shared prefixes" structure is what makes tries so effective for prefix-based operations: "cat" and "car" and "cart" all share the same "ca"/"car" path and only branch where they actually differ. That single property is why tries are the standard structure behind autocomplete and search-as-you-type suggestions, spell-checkers, and IP routing tables (where the longest matching prefix determines the route) — all workloads built entirely around "find everything starting with X."

"cat", "car", "cart", and "dog" stored in one trie
cdaortg•cdaortg
Character nodeEnd of a word

Both insertion and search walk one character at a time from the root: insertion follows existing edges where they already exist and creates new nodes only where the path doesn't yet exist, then marks the final node as end-of-word. Search does the same walk — if it ever needs an edge that doesn't exist, the word (or prefix) definitely isn't in the trie; if it reaches the end of the word, it still has to check that node's end-of-word flag, because the path existing only proves the string is a prefix of something, not that it was inserted as its own word.

Algorithm Steps

  1. Insertion: start at the root; for each character in the word, follow the matching child edge if it exists, or create a new node for it if it doesn't; after the last character, mark that node as end-of-word
  2. Search: start at the root; for each character, follow the matching child edge — if it's missing at any point, the word isn't in the trie
  3. If every character is matched, the word is in the trie only if the final node's end-of-word flag is set — otherwise it's merely a prefix of other stored words

Time Complexity

  • Time Complexity: Insertion and search both cost O(L), where L is the word's length.
  • Space Complexity: Up to O(total characters) across all inserted words, though shared prefixes reduce this in practice.

Time Complexity Analysis

Advertisement

Both operations run in O(L) time, where L is the length of the word — not O(log n) or O(n) in terms of how many words are already stored. A hash set can also do exact lookups in roughly that time, but it can't efficiently answer "what words start with this prefix" the way a trie can, since a matching prefix's subtree already holds exactly the words that share it.

Daily DSA Challenge by Scale Engineer

Insert words to build the trie, then search and watch it follow one letter at a time

Trie is empty
No trie yet — insert a word or generate random words
Character nodeEnd of a wordRoot (empty prefix)Search pathNewly created

Test Your Knowledge before moving forward!

Trie (Prefix Tree) Quiz

How it works:

  • +1 point for each correct answer
  • 0 points for wrong answers
  • -0.5 point penalty for viewing explanations
  • Earn stars based on your final score (max 5 stars)

Trie Implementation

// Trie (Prefix Tree) node
class TrieNode {
  constructor() {
    this.children = {}; // character -> TrieNode
    this.isEnd = false;  // true if a word ends at this node
  }
}

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

  insert(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children[ch]) {
        node.children[ch] = new TrieNode();
      }
      node = node.children[ch];
    }
    node.isEnd = true;
  }

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

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

  _walk(str) {
    let node = this.root;
    for (const ch of str) {
      if (!node.children[ch]) return null;
      node = node.children[ch];
    }
    return node;
  }
}

// Usage example
const trie = new Trie();
["cat", "car", "cart", "dog"].forEach((w) => trie.insert(w));

trie.search("car");       // true
trie.search("ca");        // false — only a prefix, not inserted as a word
trie.startsWith("ca");    // true — "cat"/"car"/"cart" all start with "ca"

Done With the Learning

Mark Trie (Prefix Tree) as done and view it on your dashboard

Explore Other Tree Topics

Red-Black Tree

B-Tree

Segment Tree

Fenwick Tree

AVL Balancing

BST Insertion

BST Searching