Stage 4: Advanced Techniques·Trie & Bitwise

Medium#2088 min readTrieDesignLeetCode

Implement Trie

Fixed-array trie

Build the basic trie. In Rust, use Vec<Option<Box<TrieNode>>> or arena alloc.

Published Apr 16, 2026

Problem

Design a data structure with three operations, each on a lowercase-letter word:

insert(word) — store the word.
search(word) — has this exact word been inserted before?
startsWith(prefix) — has any stored word been inserted that begins with this prefix?

All three operations should run in time proportional to the length of the argument, independent of how many words have already been inserted.

Input

["Trie","insert","search","search","startsWith","insert","search"] with args ["apple"],["apple"],["app"],["app"],["app"],["app"]

Output

[null, null, true, false, true, null, true]

Explanation

search('app') is false after inserting only 'apple' because 'app' is a prefix, not a stored word. After inserting 'app' the same search returns true.

Input

insert("bad"), search("ba"), startsWith("ba")

Output

[null, false, true]

Explanation

Searching 'ba' fails — no terminal marker at that depth — but startsWith succeeds because 'bad' was inserted.

Intuition

A HashSet<String> answers search in O(L) but turns startsWith into a linear scan over every key. A sorted array of strings reverses the trade: prefix queries via binary search, but insertion moves O(N · L) characters.

The trie (or prefix tree) is the structure designed to answer both questions in a single walk. Every stored word is a path from the root to a node flagged as "end of word". Prefix membership is "can I walk down this path without falling off the tree?". Word membership adds the extra check "and does the final node have the end-of-word flag?".

The only interesting design decision is how to store a node's children: a 26-slot fixed array (cheap reads, wastes memory on sparse trees) or a HashMap/BTreeMap (compact, one hash per step). For lowercase ASCII with dense tries the array wins — a pointer dereference beats a hash every time.

Approach

HashMap Children

TimeO(L)

SpaceO(N · L)

Each node stores a map from character to child node plus a boolean end. insert walks the map and creates missing children. search walks and checks end at the final node. startsWith walks without caring about end.

This version is compact for sparse alphabets (unicode, mixed case) and avoids the 26-slot overhead per node. The per-step cost is a hash lookup, but the big-O remains O(L) per operation.

use std::collections::HashMap;

#[derive(Default)]
struct TrieNode {
    children: HashMap<char, TrieNode>,
    end: bool,
}

pub struct Trie {
    root: TrieNode,
}

impl Trie {
    pub fn new() -> Self {
        Self { root: TrieNode::default() }
    }

    pub fn insert(&mut self, word: String) {
        let mut node = &mut self.root;
        for ch in word.chars() {
            node = node.children.entry(ch).or_default();
        }
        node.end = true;
    }

    pub fn search(&self, word: String) -> bool {
        self.walk(&word).map_or(false, |n| n.end)
    }

    pub fn starts_with(&self, prefix: String) -> bool {
        self.walk(&prefix).is_some()
    }
}

impl Trie {
    fn walk(&self, s: &str) -> Option<&TrieNode> {
        let mut node = &self.root;
        for ch in s.chars() {
            node = node.children.get(&ch)?;
        }
        Some(node)
    }
}

Rust · runnable

class Trie {
  private children: Map<string, Trie> = new Map();
  private end = false;

  insert(word: string): void {
    let node: Trie = this;
    for (const ch of word) {
      let next = node.children.get(ch);
      if (!next) {
        next = new Trie();
        node.children.set(ch, next);
      }
      node = next;
    }
    node.end = true;
  }

  search(word: string): boolean {
    const node = this.walk(word);
    return node !== null && node.end;
  }

  startsWith(prefix: string): boolean {
    return this.walk(prefix) !== null;
  }

  private walk(s: string): Trie | null {
    let node: Trie = this;
    for (const ch of s) {
      const next = node.children.get(ch);
      if (!next) return null;
      node = next;
    }
    return node;
  }
}

TypeScript · runnable

Fixed-size Array

TimeO(L)

SpaceO(26 · N · L)

Recommended

Children are stored in a fixed [Option<Box<TrieNode>>; 26]. The per-step cost drops from a hash to an index calculation (ch as usize - 'a' as usize), which is consistently the fastest option for lowercase ASCII tries.

The memory overhead is real — an internal node with one child still allocates 26 slots — but when the alphabet is small and the tree is dense (shared prefixes like English dictionary words) the tradeoff favors speed.

#[derive(Default)]
struct TrieNode {
    children: [Option<Box<TrieNode>>; 26],
    end: bool,
}

pub struct Trie {
    root: TrieNode,
}

impl Trie {
    pub fn new() -> Self {
        Self { root: TrieNode::default() }
    }

    pub fn insert(&mut self, word: String) {
        let mut node = &mut self.root;
        for ch in word.bytes() {
            let idx = (ch - b'a') as usize;
            node = node.children[idx].get_or_insert_with(|| Box::new(TrieNode::default()));
        }
        node.end = true;
    }

    pub fn search(&self, word: String) -> bool {
        self.walk(&word).map_or(false, |n| n.end)
    }

    pub fn starts_with(&self, prefix: String) -> bool {
        self.walk(&prefix).is_some()
    }
}

impl Trie {
    fn walk(&self, s: &str) -> Option<&TrieNode> {
        let mut node = &self.root;
        for ch in s.bytes() {
            let idx = (ch - b'a') as usize;
            node = node.children[idx].as_deref()?;
        }
        Some(node)
    }
}

Rust · runnable

class Trie {
  private children: Array<Trie | null> = new Array(26).fill(null);
  private end = false;

  insert(word: string): void {
    let node: Trie = this;
    for (let i = 0; i < word.length; i++) {
      const idx= word.charCodeAt(i) - 97;
      let next= node.children[idx];
      if (next= null) {
        next= new Trie();
        node.children[idx]= next;
      }
      node= next;
    }
    node.end= true;
  }

  search(word: string): boolean {
    const node= this.walk(word);
    return node = null && node.end;
  }

  startsWith(prefix: string): boolean {
    return this.walk(prefix) = null;
  }

  private walk(s: string): Trie | null {
    let node: Trie= this;
    for (let i= 0; i < s.length; i++) {
      const idx= s.charCodeAt(i) - 97;
      const next= node.children[idx];
      if (next= null) return null;
      node= next;
    }
    return node;
  }
}

TypeScript · runnable

Language notes:

Rust — get_or_insert_with collapses the "check then insert" dance into one borrow. as_deref converts Option<Box<T>> into Option<&T> without re-borrowing the slot.
TypeScript — V8 is happy to treat a 26-slot array as a dense packed array of pointers; no surprise deoptimization.

Trace

Insert "apple" then "app" into an empty trie (fixed-array variant). Each row shows the state after one step of the walk:

op	char	node index	created?	end flag
insert apple	a	root[0]	yes	false
insert apple	p	a[15]	yes	false
insert apple	p	ap[15]	yes	false
insert apple	l	app[11]	yes	false
insert apple	e	appl[4]	yes	true
insert app	a	root[0]	no	false
insert app	p	a[15]	no	false
insert app	p	ap[15]	no	true

After both inserts, the path a → p → p has end = true (added by the second insert), and the deeper node for apple still has end = true. A search('app') call walks to the second p and returns true because its end flag was set by the second insert.

Edge cases

Empty input string — walk returns the root. startsWith('') is trivially true; search('') depends on whether the root has end set (which only happens if the empty string was inserted).
Single character — degenerate path of length one; still works identically.
Repeated insert of the same word — traverses existing nodes, re-sets end = true. Idempotent.
Long shared prefix — "apple" then "application" share five nodes; the two words diverge only at the sixth character.

💡

Tip

LeetCode's test harness allocates every trie operation as an entry in two parallel arrays (method names + arguments). Our runner here uses the same contract — a runTrie(ops) wrapper so each benchmark iteration rebuilds a fresh tree.

Takeaway

The trie is the right answer whenever you need prefix-based queries on a large set of strings. Autocomplete, router path dispatch, genome k-mer indexing, IP prefix matching — they all fall out of this one structure.

The fixed-array variant wins on small alphabets (lowercase ASCII, DNA bases, hex digits). The hashmap variant wins on sparse/unicode alphabets. Pick deliberately.

Once you have the trie, problem #421's "maximum XOR pair" reduces to inserting the bits of each integer as a 32-level binary trie and greedily walking opposite bits at each level — same structure, different alphabet.

Medium#421

Maximum XOR of Two Numbers in Array

Binary trie. Insert all numbers, then for each number greedily pick opposite bits.

Hard#1707

Maximum XOR With an Element From Array

Offline sort + incremental trie insertion + XOR query.

More in Trie & Bitwise

Medium#421

Maximum XOR of Two Numbers in Array

Binary trie. Insert all numbers, then for each number greedily pick opposite bits.

Hard#1707

Maximum XOR With an Element From Array

Offline sort + incremental trie insertion + XOR query.

Hard#1835

Find XOR Sum of All Pairs Bitwise AND

Pure bit-level reasoning. Think about each bit independently.

View #208 on LeetCode