Implementing a Trie: The TrieNode and Class Structure

To implement a trie you need two pieces: a node that holds links to its children plus an end-of-word marker, and a class that owns the root node and exposes the operations. This page builds the node and the empty class skeleton; the next page fills in insert, search, and prefix. If you have not yet, skim the tries introduction first.

Design choice: how to store children

Every node maps a single character to a child node. There are two common ways to store that map:

• Hash map (char → node). Flexible, works for any alphabet (Unicode, symbols), uses memory only for characters that actually appear. This is the default we use here.
• Fixed-size array (e.g. 26 slots for lowercase a–z). Slightly faster constant factor and no hashing, but wastes space when the alphabet is large or sparse.

We use a map because it is the most portable across the four languages and handles any alphabet. The complexity is the same either way.

Going deeper: With a 26-slot array, index a child as node.children[ch - 'a']. It trades memory for a tiny speed gain — worthwhile in tight competitive-programming loops, overkill for most apps.

The TrieNode

A node stores its children and whether a word ends at it. Nothing else is required for a basic trie.

struct TrieNode {
    std::unordered_map<char, TrieNode*> children;
    bool isEnd = false;
};

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean isEnd = false;
}

class TrieNode {
  constructor() {
    this.children = new Map(); // char -> TrieNode
    this.isEnd = false;
  }
}

class TrieNode:
    def __init__(self):
        self.children = {}     # char -> TrieNode
        self.is_end = False

The Trie class skeleton

The trie itself just owns a single root node — an empty node that represents the empty prefix "". Every word is a path starting from this root. Here is the class with a constructor; the methods come on the next page.

class Trie {
    TrieNode* root;
public:
    Trie() { root = new TrieNode(); }
    // insert, search, startsWith go here
    ~Trie() { freeNode(root); }
private:
    void freeNode(TrieNode* node) {
        for (auto& [ch, child] : node->children) freeNode(child);
        delete node;
    }
};

class Trie {
    private final TrieNode root;

    public Trie() {
        root = new TrieNode();
    }
    // insert, search, startsWith go here
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }
  // insert, search, startsWith go here
}

class Trie:
    def __init__(self):
        self.root = TrieNode()
    # insert, search, starts_with go here

For beginners: The root holds no character of its own. Think of it as the starting line — the first real character of every word lives one level below it. The freeNode helper in the C++ version recursively releases memory; garbage-collected languages (Java, JS, Python) do this automatically.

Why a map plus a flag is enough

These two fields cover everything a basic trie needs:

• The children map lets you walk character by character in O(1) per step (average, for a hash map).
• The isEnd flag distinguishes a stored word from a mere prefix. Without it you could not tell that car is a word when card extends past it.

Some variants add extra fields — a count of words passing through a node (to support deletion and prefix counts), or a stored value (turning the trie into a map). Start with the minimal node; add fields only when a problem demands them.

Complexity of the structure

• Space: O(total characters inserted) in the worst case, less when words share prefixes.
• Per-node overhead: one map plus one boolean. The map keys are the branching characters.

With the node and class skeleton in place, move on to the heart of the structure: trie operations — insert, search, and prefix.