A trie (prefix tree) stores a set of words as a tree of characters, so that every operation costs time proportional to the length of the word — not to the number of words — and so that words sharing a prefix share a path. It is the structure behind autocomplete, spell-checkers and IP routing tables.

Trie for { geeks, geek, bad, bat, cat, cut } — "geek" and "geeks" share one path, "ba" is a prefix of two words

         (root)
  ┌────────┼────────┐
  b        c        g
  │     ┌──┴──┐     │
  a     a     u     e
┌─┴─┐   │     │     │
d*  t*  t*    t*    e
                    │
                    k*          * = isEndOfWord
                    │
                    s*

Tries are the right choice when a dictionary of words must support these operations efficiently:

Search — is this exact word in the dictionary?
Insert — add a word.
Delete — remove a word (without disturbing words that share its prefix).
Prefix search — does any word start with pre? List them all (autocomplete).
Lexicographic ordering — a pre-order traversal visits the words in sorted order for free.

Operation	Trie	Hash table
Search	Θ(word_len)	Θ(word_len) average
Insert	Θ(word_len)	Θ(word_len) average
Delete	Θ(word_len)	Θ(word_len) average
Prefix search	Θ(prefix_len)	not supported
Lexicographic ordering	Θ(output_len)	not supported (needs a sort)
Memory	high — up to 26 pointers per node	low

Trie representation

For lowercase English words each node holds an array of 26 child pointers (index ch − 'a') and a boolean isEndOfWord. The characters themselves are not stored in the nodes — they are implied by the array index on the way down.

Python

class TrieNode:
    def __init__(self):
        self.child = [None] * 26          # child[i] → node for chr(ord('a') + i), or None
        self.is_end_of_word = False       # True ⇔ the path from the root spells a stored word

root = TrieNode()                         # the empty trie: a root with no children
print(sum(c is not None for c in root.child), root.is_end_of_word)

Output

0 False

Field	Meaning
`child[26]`	one slot per letter; `None`/`nullptr` means no word continues with that letter
`isEndOfWord`	marks a complete word — needed because `geek` must be found while `gee` must not

Insert, search and prefix search

Start at the root
with the first character of the key.
Follow child[ch − 'a']
insert: create the node if it is missing — search: return false if it is missing.
At the last character
insert: set isEndOfWord = true — search: return isEndOfWord — startsWith: return true.

Python

class TrieNode:
    def __init__(self):
        self.child = [None] * 26
        self.is_end_of_word = False

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

    def insert(self, key):
        node = self.root
        for ch in key:
            i = ord(ch) - ord('a')
            if node.child[i] is None:            # extend the path where it stops
                node.child[i] = TrieNode()
            node = node.child[i]
        node.is_end_of_word = True               # mark the complete word

    def _walk(self, key):                        # node where `key` ends, or None
        node = self.root
        for ch in key:
            node = node.child[ord(ch) - ord('a')]
            if node is None:
                return None
        return node

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

    def starts_with(self, prefix):
        return self._walk(prefix) is not None

    def words(self):                             # pre-order traversal → lexicographic order
        out = []
        def dfs(node, prefix):
            if node.is_end_of_word:
                out.append(prefix)
            for i, c in enumerate(node.child):
                if c is not None:
                    dfs(c, prefix + chr(ord('a') + i))
        dfs(self.root, "")
        return out

trie = Trie()
for w in ["geeks", "geek", "bad", "bat", "cat", "cut"]:
    trie.insert(w)
for w in ["geek", "gee", "cut", "dog"]:
    print(f"search {w}:", "true" if trie.search(w) else "false")
for pre in ["ge", "do"]:
    print(f"startsWith {pre}:", "true" if trie.starts_with(pre) else "false")
print("words:", " ".join(trie.words()))

C++

#include <iostream>
#include <string>
#include <vector>
using namespace std;

struct TrieNode {
    TrieNode* child[26] = {};
    bool isEndOfWord = false;
};

class Trie {
    TrieNode* root = new TrieNode();
    TrieNode* walk(const string& key) const {           // node where `key` ends, or nullptr
        TrieNode* node = root;
        for (char ch : key) {
            node = node->child[ch - 'a'];
            if (!node) return nullptr;
        }
        return node;
    }
    void dfs(TrieNode* node, string& prefix, vector<string>& out) const {
        if (node->isEndOfWord) out.push_back(prefix);
        for (int i = 0; i < 26; i++)
            if (node->child[i]) {
                prefix.push_back('a' + i);
                dfs(node->child[i], prefix, out);
                prefix.pop_back();
            }
    }
public:
    void insert(const string& key) {
        TrieNode* node = root;
        for (char ch : key) {
            int i = ch - 'a';
            if (!node->child[i]) node->child[i] = new TrieNode();   // extend the path where it stops
            node = node->child[i];
        }
        node->isEndOfWord = true;                                   // mark the complete word
    }
    bool search(const string& key) const { TrieNode* n = walk(key); return n && n->isEndOfWord; }
    bool startsWith(const string& prefix) const { return walk(prefix) != nullptr; }
    vector<string> words() const { vector<string> out; string p; dfs(root, p, out); return out; }   // sorted
};

int main() {
    Trie trie;
    for (string w : {"geeks", "geek", "bad", "bat", "cat", "cut"}) trie.insert(w);
    for (string w : {"geek", "gee", "cut", "dog"}) cout << "search " << w << ": " << (trie.search(w) ? "true" : "false") << "\n";
    for (string p : {"ge", "do"}) cout << "startsWith " << p << ": " << (trie.startsWith(p) ? "true" : "false") << "\n";
    cout << "words:";
    for (const string& w : trie.words()) cout << " " << w;
    cout << "\n";
}

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static class TrieNode {
        TrieNode[] child = new TrieNode[26];
        boolean isEndOfWord;
    }

    static class Trie {
        TrieNode root = new TrieNode();

        void insert(String key) {
            TrieNode node = root;
            for (char ch : key.toCharArray()) {
                int i = ch - 'a';
                if (node.child[i] == null) node.child[i] = new TrieNode();   // extend the path where it stops
                node = node.child[i];
            }
            node.isEndOfWord = true;                                          // mark the complete word
        }
        TrieNode walk(String key) {                                           // node where key ends, or null
            TrieNode node = root;
            for (char ch : key.toCharArray()) {
                node = node.child[ch - 'a'];
                if (node == null) return null;
            }
            return node;
        }
        boolean search(String key) { TrieNode n = walk(key); return n != null && n.isEndOfWord; }
        boolean startsWith(String prefix) { return walk(prefix) != null; }
        List<String> words() { List<String> out = new ArrayList<>(); dfs(root, new StringBuilder(), out); return out; }
        void dfs(TrieNode node, StringBuilder prefix, List<String> out) {     // pre-order → sorted
            if (node.isEndOfWord) out.add(prefix.toString());
            for (int i = 0; i < 26; i++)
                if (node.child[i] != null) {
                    prefix.append((char) ('a' + i));
                    dfs(node.child[i], prefix, out);
                    prefix.setLength(prefix.length() - 1);
                }
        }
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        for (String w : new String[]{"geeks", "geek", "bad", "bat", "cat", "cut"}) trie.insert(w);
        for (String w : new String[]{"geek", "gee", "cut", "dog"}) System.out.println("search " + w + ": " + trie.search(w));
        for (String p : new String[]{"ge", "do"}) System.out.println("startsWith " + p + ": " + trie.startsWith(p));
        System.out.println("words: " + String.join(" ", trie.words()));
    }
}

JavaScript

class TrieNode {
    constructor() { this.child = new Array(26).fill(null); this.isEndOfWord = false; }
}

class Trie {
    constructor() { this.root = new TrieNode(); }
    insert(key) {
        let node = this.root;
        for (const ch of key) {
            const i = ch.charCodeAt(0) - 97;
            if (node.child[i] === null) node.child[i] = new TrieNode();   // extend the path where it stops
            node = node.child[i];
        }
        node.isEndOfWord = true;                                           // mark the complete word
    }
    walk(key) {                                                            // node where key ends, or null
        let node = this.root;
        for (const ch of key) {
            node = node.child[ch.charCodeAt(0) - 97];
            if (node === null) return null;
        }
        return node;
    }
    search(key) { const n = this.walk(key); return n !== null && n.isEndOfWord; }
    startsWith(prefix) { return this.walk(prefix) !== null; }
    words() {                                                              // pre-order → sorted
        const out = [];
        const dfs = (node, prefix) => {
            if (node.isEndOfWord) out.push(prefix);
            node.child.forEach((c, i) => { if (c !== null) dfs(c, prefix + String.fromCharCode(97 + i)); });
        };
        dfs(this.root, "");
        return out;
    }
}

const trie = new Trie();
for (const w of ["geeks", "geek", "bad", "bat", "cat", "cut"]) trie.insert(w);
for (const w of ["geek", "gee", "cut", "dog"]) console.log(`search ${w}:`, trie.search(w));
for (const p of ["ge", "do"]) console.log(`startsWith ${p}:`, trie.startsWith(p));
console.log("words:", trie.words().join(" "));

Output

search geek: true
search gee: false
search cut: true
search dog: false
startsWith ge: true
startsWith do: false
words: bad bat cat cut geek geeks

Time O(L) per insert / search / startsWith for a word of length L · Space O(total characters × alphabet) for the trie

Delete

Deleting must remove the word without breaking any other word that shares its path. geeks and geek share g-e-e-k; deleting geeks may remove only the s node, and deleting geek must only clear a flag.

Recurse to the node of the last character
depth == len(key): unmark isEndOfWord.
Is this node now useless?
No children and not the end of any word → return null so the parent drops its pointer.
Walk back up
Each parent re-checks: if it is not a word end and has no children left, it is removed as well. The first node that still serves another word stops the chain.

The three cases: remove a leaf, stop at a shared node, remove a whole chain

delete("geeks")              delete("bad")                 delete("geek")
g-e-e-k*-s*                  b-a-d*                        g-e-e-k*
         └ unmark s,         a-t*                                  └ unmark k; k is a leaf → remove
           s has no          └ unmark d; d is a leaf        e has no children now → remove
           children →          → remove d; a still has     e → remove, g → remove
           remove s            child t → stop              root stays (it also has b, c)
k keeps its * — geek lives on

Python

class TrieNode:
    def __init__(self):
        self.child = [None] * 26
        self.is_end_of_word = False

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

    def insert(self, key):
        node = self.root
        for ch in key:
            i = ord(ch) - ord('a')
            if node.child[i] is None:
                node.child[i] = TrieNode()
            node = node.child[i]
        node.is_end_of_word = True

    def _walk(self, key):
        node = self.root
        for ch in key:
            node = node.child[ord(ch) - ord('a')]
            if node is None:
                return None
        return node

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

    def starts_with(self, prefix):
        return self._walk(prefix) is not None

    def delete(self, key):
        def _delete(node, depth):                       # returns the node to keep, or None to drop it
            if node is None:
                return None
            if depth == len(key):
                node.is_end_of_word = False             # the word itself is gone …
            else:
                i = ord(key[depth]) - ord('a')
                node.child[i] = _delete(node.child[i], depth + 1)
            if node.is_end_of_word or any(c is not None for c in node.child):
                return node                             # … but this node still serves other words
            return None                                 # useless node: unlink it
        self.root = _delete(self.root, 0) or TrieNode()

    def words(self):
        out = []
        def dfs(node, prefix):
            if node.is_end_of_word:
                out.append(prefix)
            for i, c in enumerate(node.child):
                if c is not None:
                    dfs(c, prefix + chr(ord('a') + i))
        dfs(self.root, "")
        return out

t = Trie()
for w in ["geeks", "geek", "bad", "bat", "cat", "cut"]:
    t.insert(w)
b = lambda v: "true" if v else "false"
t.delete("geeks"); print(f"after delete(geeks): geeks={b(t.search('geeks'))} geek={b(t.search('geek'))}")
t.delete("bad");   print(f"after delete(bad): bad={b(t.search('bad'))} bat={b(t.search('bat'))}")
t.delete("geek");  print(f"after delete(geek): geek={b(t.search('geek'))} startsWith(ge)={b(t.starts_with('ge'))}")
print("words:", " ".join(t.words()))

C++

#include <iostream>
#include <string>
#include <vector>
using namespace std;

struct TrieNode {
    TrieNode* child[26] = {};
    bool isEndOfWord = false;
    bool hasChild() const { for (TrieNode* c : child) if (c) return true; return false; }
};

class Trie {
    TrieNode* root = new TrieNode();
    TrieNode* walk(const string& key) const {
        TrieNode* node = root;
        for (char ch : key) { node = node->child[ch - 'a']; if (!node) return nullptr; }
        return node;
    }
    static TrieNode* remove(TrieNode* node, const string& key, size_t depth) {   // node to keep, or nullptr
        if (!node) return nullptr;
        if (depth == key.size()) {
            node->isEndOfWord = false;                              // the word itself is gone …
        } else {
            int i = key[depth] - 'a';
            node->child[i] = remove(node->child[i], key, depth + 1);
        }
        if (node->isEndOfWord || node->hasChild()) return node;     // … but this node still serves other words
        delete node;                                                // useless node: unlink it
        return nullptr;
    }
    void dfs(TrieNode* node, string& prefix, vector<string>& out) const {
        if (node->isEndOfWord) out.push_back(prefix);
        for (int i = 0; i < 26; i++)
            if (node->child[i]) { prefix.push_back('a' + i); dfs(node->child[i], prefix, out); prefix.pop_back(); }
    }
public:
    void insert(const string& key) {
        TrieNode* node = root;
        for (char ch : key) {
            int i = ch - 'a';
            if (!node->child[i]) node->child[i] = new TrieNode();
            node = node->child[i];
        }
        node->isEndOfWord = true;
    }
    bool search(const string& key) const { TrieNode* n = walk(key); return n && n->isEndOfWord; }
    bool startsWith(const string& p) const { return walk(p) != nullptr; }
    void erase(const string& key) { root = remove(root, key, 0); if (!root) root = new TrieNode(); }
    vector<string> words() const { vector<string> out; string p; dfs(root, p, out); return out; }
};

const char* b(bool v) { return v ? "true" : "false"; }

int main() {
    Trie t;
    for (string w : {"geeks", "geek", "bad", "bat", "cat", "cut"}) t.insert(w);
    t.erase("geeks"); cout << "after delete(geeks): geeks=" << b(t.search("geeks")) << " geek=" << b(t.search("geek")) << "\n";
    t.erase("bad");   cout << "after delete(bad): bad=" << b(t.search("bad")) << " bat=" << b(t.search("bat")) << "\n";
    t.erase("geek");  cout << "after delete(geek): geek=" << b(t.search("geek")) << " startsWith(ge)=" << b(t.startsWith("ge")) << "\n";
    cout << "words:";
    for (const string& w : t.words()) cout << " " << w;
    cout << "\n";
}

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static class TrieNode {
        TrieNode[] child = new TrieNode[26];
        boolean isEndOfWord;
        boolean hasChild() { for (TrieNode c : child) if (c != null) return true; return false; }
    }

    static class Trie {
        TrieNode root = new TrieNode();

        void insert(String key) {
            TrieNode node = root;
            for (char ch : key.toCharArray()) {
                int i = ch - 'a';
                if (node.child[i] == null) node.child[i] = new TrieNode();
                node = node.child[i];
            }
            node.isEndOfWord = true;
        }
        TrieNode walk(String key) {
            TrieNode node = root;
            for (char ch : key.toCharArray()) { node = node.child[ch - 'a']; if (node == null) return null; }
            return node;
        }
        boolean search(String key) { TrieNode n = walk(key); return n != null && n.isEndOfWord; }
        boolean startsWith(String p) { return walk(p) != null; }

        void delete(String key) { root = delete(root, key, 0); if (root == null) root = new TrieNode(); }
        TrieNode delete(TrieNode node, String key, int depth) {           // node to keep, or null to drop it
            if (node == null) return null;
            if (depth == key.length()) {
                node.isEndOfWord = false;                                 // the word itself is gone …
            } else {
                int i = key.charAt(depth) - 'a';
                node.child[i] = delete(node.child[i], key, depth + 1);
            }
            if (node.isEndOfWord || node.hasChild()) return node;         // … but this node still serves other words
            return null;                                                  // useless node: unlink it
        }
        List<String> words() { List<String> out = new ArrayList<>(); dfs(root, new StringBuilder(), out); return out; }
        void dfs(TrieNode node, StringBuilder prefix, List<String> out) {
            if (node.isEndOfWord) out.add(prefix.toString());
            for (int i = 0; i < 26; i++)
                if (node.child[i] != null) {
                    prefix.append((char) ('a' + i)); dfs(node.child[i], prefix, out); prefix.setLength(prefix.length() - 1);
                }
        }
    }

    public static void main(String[] args) {
        Trie t = new Trie();
        for (String w : new String[]{"geeks", "geek", "bad", "bat", "cat", "cut"}) t.insert(w);
        t.delete("geeks"); System.out.println("after delete(geeks): geeks=" + t.search("geeks") + " geek=" + t.search("geek"));
        t.delete("bad");   System.out.println("after delete(bad): bad=" + t.search("bad") + " bat=" + t.search("bat"));
        t.delete("geek");  System.out.println("after delete(geek): geek=" + t.search("geek") + " startsWith(ge)=" + t.startsWith("ge"));
        System.out.println("words: " + String.join(" ", t.words()));
    }
}

JavaScript

class TrieNode {
    constructor() { this.child = new Array(26).fill(null); this.isEndOfWord = false; }
    hasChild() { return this.child.some(c => c !== null); }
}

class Trie {
    constructor() { this.root = new TrieNode(); }
    insert(key) {
        let node = this.root;
        for (const ch of key) {
            const i = ch.charCodeAt(0) - 97;
            if (node.child[i] === null) node.child[i] = new TrieNode();
            node = node.child[i];
        }
        node.isEndOfWord = true;
    }
    walk(key) {
        let node = this.root;
        for (const ch of key) { node = node.child[ch.charCodeAt(0) - 97]; if (node === null) return null; }
        return node;
    }
    search(key) { const n = this.walk(key); return n !== null && n.isEndOfWord; }
    startsWith(p) { return this.walk(p) !== null; }

    delete(key) {
        const rec = (node, depth) => {                              // node to keep, or null to drop it
            if (node === null) return null;
            if (depth === key.length) {
                node.isEndOfWord = false;                           // the word itself is gone …
            } else {
                const i = key.charCodeAt(depth) - 97;
                node.child[i] = rec(node.child[i], depth + 1);
            }
            if (node.isEndOfWord || node.hasChild()) return node;   // … but this node still serves other words
            return null;                                            // useless node: unlink it
        };
        this.root = rec(this.root, 0) ?? new TrieNode();
    }
    words() {
        const out = [];
        const dfs = (node, prefix) => {
            if (node.isEndOfWord) out.push(prefix);
            node.child.forEach((c, i) => { if (c !== null) dfs(c, prefix + String.fromCharCode(97 + i)); });
        };
        dfs(this.root, "");
        return out;
    }
}

const t = new Trie();
for (const w of ["geeks", "geek", "bad", "bat", "cat", "cut"]) t.insert(w);
t.delete("geeks"); console.log(`after delete(geeks): geeks=${t.search("geeks")} geek=${t.search("geek")}`);
t.delete("bad");   console.log(`after delete(bad): bad=${t.search("bad")} bat=${t.search("bat")}`);
t.delete("geek");  console.log(`after delete(geek): geek=${t.search("geek")} startsWith(ge)=${t.startsWith("ge")}`);
console.log("words:", t.words().join(" "));

Output

after delete(geeks): geeks=false geek=true
after delete(bad): bad=false bat=true
after delete(geek): geek=false startsWith(ge)=false
words: bat cat cut

Time O(L) — one pass down and one pass back up · Space O(L) recursion depth

Count distinct rows in a binary matrix

Given a binary matrix (every entry 0 or 1), count how many distinct rows it has.

Naive: for every row, compare it with every earlier row; count it if it matches none. R rows, each compared with up to R others, C entries per comparison.

Python

def count_distinct_rows(matrix):
    res = 0
    for i, row in enumerate(matrix):
        if all(row != matrix[j] for j in range(i)):     # matches no earlier row → new
            res += 1
    return res

print(count_distinct_rows([[1, 0, 0], [1, 1, 1], [1, 0, 0], [1, 1, 1]]))

Output

Time O(R² · C) · Space O(1)

A binary trie of the rows: equal rows walk the same path and hit the same leaf

rows: 1 0 0 / 1 1 1 / 1 0 0 / 1 1 1

         (root)
           │ 1
           ●
      0 ┌──┴──┐ 1
        ●     ●
      0 │     │ 1
        ●*    ●*          two marked leaves → 2 distinct rows

Python

class Node:
    def __init__(self):
        self.child = [None, None]          # child[0] for a 0, child[1] for a 1
        self.is_end = False

def insert_row(root, row):                 # True if the row was not present before
    node = root
    for bit in row:
        if node.child[bit] is None:
            node.child[bit] = Node()
        node = node.child[bit]
    if node.is_end:
        return False                       # an identical row ended here already
    node.is_end = True
    return True

def count_distinct_rows(matrix):
    root = Node()
    return sum(1 for row in matrix if insert_row(root, row))

matrix = [[1, 0, 0], [1, 1, 1], [1, 0, 0], [1, 1, 1]]
print("distinct rows:", count_distinct_rows(matrix))

C++

#include <iostream>
#include <vector>
using namespace std;

struct Node {
    Node* child[2] = {nullptr, nullptr};   // child[0] for a 0, child[1] for a 1
    bool isEnd = false;
};

bool insertRow(Node* root, const vector<int>& row) {   // true if the row was not present before
    Node* node = root;
    for (int bit : row) {
        if (!node->child[bit]) node->child[bit] = new Node();
        node = node->child[bit];
    }
    if (node->isEnd) return false;                     // an identical row ended here already
    node->isEnd = true;
    return true;
}

int countDistinctRows(const vector<vector<int>>& matrix) {
    Node* root = new Node();
    int res = 0;
    for (const auto& row : matrix)
        if (insertRow(root, row)) res++;
    return res;
}

int main() {
    vector<vector<int>> matrix = {{1, 0, 0}, {1, 1, 1}, {1, 0, 0}, {1, 1, 1}};
    cout << "distinct rows: " << countDistinctRows(matrix) << "\n";
}

Java

public class Main {
    static class Node {
        Node[] child = new Node[2];        // child[0] for a 0, child[1] for a 1
        boolean isEnd;
    }

    static boolean insertRow(Node root, int[] row) {   // true if the row was not present before
        Node node = root;
        for (int bit : row) {
            if (node.child[bit] == null) node.child[bit] = new Node();
            node = node.child[bit];
        }
        if (node.isEnd) return false;                  // an identical row ended here already
        node.isEnd = true;
        return true;
    }

    static int countDistinctRows(int[][] matrix) {
        Node root = new Node();
        int res = 0;
        for (int[] row : matrix)
            if (insertRow(root, row)) res++;
        return res;
    }

    public static void main(String[] args) {
        int[][] matrix = {{1, 0, 0}, {1, 1, 1}, {1, 0, 0}, {1, 1, 1}};
        System.out.println("distinct rows: " + countDistinctRows(matrix));
    }
}

JavaScript

class Node {
    constructor() { this.child = [null, null]; this.isEnd = false; }   // child[0] for a 0, child[1] for a 1
}

function insertRow(root, row) {               // true if the row was not present before
    let node = root;
    for (const bit of row) {
        if (node.child[bit] === null) node.child[bit] = new Node();
        node = node.child[bit];
    }
    if (node.isEnd) return false;             // an identical row ended here already
    node.isEnd = true;
    return true;
}

function countDistinctRows(matrix) {
    const root = new Node();
    let res = 0;
    for (const row of matrix) if (insertRow(root, row)) res++;
    return res;
}

const matrix = [[1, 0, 0], [1, 1, 1], [1, 0, 0], [1, 1, 1]];
console.log("distinct rows:", countDistinctRows(matrix));

Output

distinct rows: 2

Time O(R · C) · Space O(R · C) for the trie in the worst case

Interview Q&A

When would you choose a trie over a hash map?

What is the space complexity of a trie, and how can it be reduced?

How do you implement autocomplete with a trie?

Why does a trie give lexicographic order for free?

What goes wrong if delete just clears the end-of-word flag?