Tries: insert, search and prefixes

Python · stations/trie.py

class Node:
    """One node of the trie: its children, one per next character, and whether a word ends here."""

    __slots__ = ("children", "is_word")

    def __init__(self):
        self.children = {}  # character -> Node
        self.is_word = False  # True when an inserted word ends exactly at this node


class Trie:
    def __init__(self):
        self.root = Node()  # the node of the empty prefix

    def insert(self, word):
        """Walks the path of word from the root, adding the nodes that are missing, then marks its end."""
        node = self.root
        for ch in word:
            child = node.children.get(ch)
            if child is None:
                child = node.children[ch] = Node()
            node = child
        node.is_word = True  # also when the whole path was already there

    def _walk(self, text):
        """The node whose path from the root spells text, or None if no inserted word starts with text."""
        node = self.root
        for ch in text:
            node = node.children.get(ch)
            if node is None:
                return None
        return node

    def search(self, word):
        """Was exactly this word inserted?"""
        node = self._walk(word)
        return node is not None and node.is_word

    def starts_with(self, prefix):
        """Does at least one inserted word start with prefix?"""
        return self._walk(prefix) is not None


STATIONS = [
    "salempur", "salem", "satna", "sangli", "surat", "sealdah", "secunderabad", "shimla", "siliguri", "solapur",
    "patna", "pune", "puri", "purna", "palghar", "panvel", "pathankot",
    "kalyan", "kalka", "katni", "kota", "kollam",
    "delhi", "delhi cantt", "delhi sarai rohilla", "new delhi",
]


def count_nodes(node):
    """The node itself and every node below it."""
    return 1 + sum(count_nodes(child) for child in node.children.values())


if __name__ == "__main__":
    trie = Trie()
    for name in STATIONS:
        trie.insert(name)
    letters = sum(len(name) for name in STATIONS)
    print(f"{len(STATIONS)} names, {letters} characters, {count_nodes(trie.root) - 1} nodes below the root")
    print()
    print("typed            a station?   starts a name?")
    for typed in ["s", "sal", "sale", "salem", "salemp", "salempur", "delhi", "delhi c", "delhi cantt", "new", "pat", "sx"]:
        station = "yes" if trie.search(typed) else "no"
        prefix = "yes" if trie.starts_with(typed) else "no"
        print(f"{typed!r:16} {station:12} {prefix}")

26 names, 179 characters, 131 nodes below the root

typed            a station?   starts a name?
's'              no           yes
'sal'            no           yes
'sale'           no           yes
'salem'          yes          yes
'salemp'         no           yes
'salempur'       yes          yes
'delhi'          yes          yes
'delhi c'        no           yes
'delhi cantt'    yes          yes
'new'            no           yes
'pat'            no           yes
'sx'             no           no

JavaScript · stations/trie.mjs

class TrieNode {
  constructor() {
    this.children = new Map(); // character -> TrieNode
    this.isWord = false; // true when an inserted word ends exactly at this node
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode(); // the node of the empty prefix
  }

  /** Walks the path of word from the root, adding the nodes that are missing, then marks its end. */
  insert(word) {
    let node = this.root;
    for (const ch of word) {
      let child = node.children.get(ch);
      if (child === undefined) {
        child = new TrieNode();
        node.children.set(ch, child);
      }
      node = child;
    }
    node.isWord = true; // also when the whole path was already there
  }

  /** The node whose path from the root spells text, or null if no inserted word starts with text. */
  walk(text) {
    let node = this.root;
    for (const ch of text) {
      node = node.children.get(ch);
      if (node === undefined) return null;
    }
    return node;
  }

  /** Was exactly this word inserted? */
  search(word) {
    const node = this.walk(word);
    return node !== null && node.isWord;
  }

  /** Does at least one inserted word start with prefix? */
  startsWith(prefix) {
    return this.walk(prefix) !== null;
  }
}

const STATIONS = [
  "salempur", "salem", "satna", "sangli", "surat", "sealdah", "secunderabad", "shimla", "siliguri", "solapur",
  "patna", "pune", "puri", "purna", "palghar", "panvel", "pathankot",
  "kalyan", "kalka", "katni", "kota", "kollam",
  "delhi", "delhi cantt", "delhi sarai rohilla", "new delhi",
];

/** The node itself and every node below it. */
function countNodes(node) {
  let count = 1;
  for (const child of node.children.values()) count += countNodes(child);
  return count;
}

const trie = new Trie();
for (const name of STATIONS) trie.insert(name);
const letters = STATIONS.reduce((sum, name) => sum + name.length, 0);
console.log(`${STATIONS.length} names, ${letters} characters, ${countNodes(trie.root) - 1} nodes below the root`);
console.log();
console.log("typed            a station?   starts a name?");
for (const typed of ["s", "sal", "sale", "salem", "salemp", "salempur", "delhi", "delhi c", "delhi cantt", "new", "pat", "sx"]) {
  const station = trie.search(typed) ? "yes" : "no";
  const prefix = trie.startsWith(typed) ? "yes" : "no";
  console.log(`${`'${typed}'`.padEnd(16)} ${station.padEnd(12)} ${prefix}`);
}

26 names, 179 characters, 131 nodes below the root

typed            a station?   starts a name?
's'              no           yes
'sal'            no           yes
'sale'           no           yes
'salem'          yes          yes
'salemp'         no           yes
'salempur'       yes          yes
'delhi'          yes          yes
'delhi c'        no           yes
'delhi cantt'    yes          yes
'new'            no           yes
'pat'            no           yes
'sx'             no           no

Java · compiled/Trie.java

import java.util.List;

public class Trie {
    private static final int SLOTS = 27; // 'a' to 'z', then the space

    private static final class Node {
        final Node[] next = new Node[SLOTS]; // every slot starts as null: no child yet
        boolean isWord; // true when an inserted word ends exactly at this node
    }

    private final Node root = new Node(); // the node of the empty prefix

    private static int slot(char c) {
        return c == ' ' ? 26 : c - 'a';
    }

    /** Walks the path of word from the root, adding the nodes that are missing, then marks its end. */
    public void insert(String word) {
        Node node = root;
        for (int i = 0; i < word.length(); i++) {
            int s = slot(word.charAt(i));
            if (node.next[s] == null) node.next[s] = new Node();
            node = node.next[s];
        }
        node.isWord = true; // also when the whole path was already there
    }

    /** The node whose path from the root spells text, or null if no inserted word starts with text. */
    private Node walk(String text) {
        Node node = root;
        for (int i = 0; i < text.length() && node != null; i++) node = node.next[slot(text.charAt(i))];
        return node;
    }

    /** Was exactly this word inserted? */
    public boolean search(String word) {
        Node node = walk(word);
        return node != null && node.isWord;
    }

    /** Does at least one inserted word start with prefix? */
    public boolean startsWith(String prefix) {
        return walk(prefix) != null;
    }

    private static int countNodes(Node node) {
        int count = 1;
        for (Node child : node.next) if (child != null) count += countNodes(child);
        return count;
    }

    static final List<String> STATIONS = List.of(
        "salempur", "salem", "satna", "sangli", "surat", "sealdah", "secunderabad", "shimla", "siliguri", "solapur",
        "patna", "pune", "puri", "purna", "palghar", "panvel", "pathankot",
        "kalyan", "kalka", "katni", "kota", "kollam",
        "delhi", "delhi cantt", "delhi sarai rohilla", "new delhi");

    public static void main(String[] args) {
        Trie trie = new Trie();
        int letters = 0;
        for (String name : STATIONS) {
            trie.insert(name);
            letters += name.length();
        }
        System.out.printf("%d names, %d characters, %d nodes below the root%n", STATIONS.size(), letters, countNodes(trie.root) - 1);
        System.out.println();
        System.out.println("typed            a station?   starts a name?");
        for (String typed : List.of("s", "sal", "sale", "salem", "salemp", "salempur", "delhi", "delhi c", "delhi cantt", "new", "pat", "sx")) {
            String station = trie.search(typed) ? "yes" : "no";
            String prefix = trie.startsWith(typed) ? "yes" : "no";
            System.out.printf("%-16s %-12s %s%n", "'" + typed + "'", station, prefix);
        }
    }
}

C++ · compiled/trie.cpp

#include <array>
#include <cstdio>
#include <string>
#include <string_view>
#include <vector>

// The nodes live in one vector and refer to each other by index: node 0 is the root, and a child index of 0 means
// "no child", because the root is nobody's child.
class Trie {
    static constexpr int kSlots = 27;  // 'a' to 'z', then the space
    std::vector<std::array<int, kSlots>> next_;  // next_[node][slot]: the index of the child, or 0
    std::vector<char> is_word_;                  // is_word_[node]: does an inserted word end here?

    static int slot(char c) { return c == ' ' ? 26 : c - 'a'; }

    // The node whose path from the root spells text, or -1 if no inserted word starts with text.
    int walk(std::string_view text) const {
        int node = 0;
        for (char c : text) {
            node = next_[node][slot(c)];
            if (node == 0) return -1;
        }
        return node;
    }

  public:
    Trie() : next_(1), is_word_(1, 0) {}  // just the root, with every slot 0

    // Walks the path of word from the root, adding the nodes that are missing, then marks its end.
    void insert(std::string_view word) {
        int node = 0;
        for (char c : word) {
            int child = next_[node][slot(c)];
            if (child == 0) {
                child = static_cast<int>(next_.size());
                next_.emplace_back();  // a new node, all slots 0; it may move the vector, so no reference is kept
                is_word_.push_back(0);
                next_[node][slot(c)] = child;
            }
            node = child;
        }
        is_word_[node] = 1;  // also when the whole path was already there
    }

    bool search(std::string_view word) const {  // was exactly this word inserted?
        int node = walk(word);
        return node != -1 && is_word_[node];
    }

    bool startsWith(std::string_view prefix) const {  // does at least one inserted word start with prefix?
        return walk(prefix) != -1;
    }

    std::size_t nodes() const { return next_.size(); }
};

int main() {
    const std::vector<std::string_view> stations = {
        "salempur", "salem", "satna", "sangli", "surat", "sealdah", "secunderabad", "shimla", "siliguri", "solapur",
        "patna", "pune", "puri", "purna", "palghar", "panvel", "pathankot",
        "kalyan", "kalka", "katni", "kota", "kollam",
        "delhi", "delhi cantt", "delhi sarai rohilla", "new delhi"};
    Trie trie;
    std::size_t letters = 0;
    for (std::string_view name : stations) {
        trie.insert(name);
        letters += name.size();
    }
    std::printf("%zu names, %zu characters, %zu nodes below the root\n\n", stations.size(), letters, trie.nodes() - 1);
    std::printf("typed            a station?   starts a name?\n");
    for (std::string_view typed : {"s", "sal", "sale", "salem", "salemp", "salempur", "delhi", "delhi c", "delhi cantt", "new", "pat", "sx"}) {
        std::string quoted = "'" + std::string(typed) + "'";
        std::printf("%-16s %-12s %s\n", quoted.c_str(), trie.search(typed) ? "yes" : "no", trie.startsWith(typed) ? "yes" : "no");
    }
}

Go · compiled/trie.go

package main

import "fmt"

const slots = 27 // 'a' to 'z', then the space

type node struct {
	next   [slots]*node // every slot starts as nil: no child yet
	isWord bool         // true when an inserted word ends exactly at this node
}

// Trie keeps its root by value: the zero Trie is an empty trie, ready to use.
type Trie struct {
	root node
}

func slot(c byte) int {
	if c == ' ' {
		return 26
	}
	return int(c - 'a')
}

// Insert walks the path of word from the root, adding the nodes that are missing, then marks its end.
func (t *Trie) Insert(word string) {
	n := &t.root
	for i := 0; i < len(word); i++ {
		s := slot(word[i])
		if n.next[s] == nil {
			n.next[s] = &node{}
		}
		n = n.next[s]
	}
	n.isWord = true // also when the whole path was already there
}

// walk returns the node whose path from the root spells text, or nil if no inserted word starts with text.
func (t *Trie) walk(text string) *node {
	n := &t.root
	for i := 0; i < len(text) && n != nil; i++ {
		n = n.next[slot(text[i])]
	}
	return n
}

// Search reports whether exactly this word was inserted.
func (t *Trie) Search(word string) bool {
	n := t.walk(word)
	return n != nil && n.isWord
}

// StartsWith reports whether at least one inserted word starts with prefix.
func (t *Trie) StartsWith(prefix string) bool {
	return t.walk(prefix) != nil
}

func countNodes(n *node) int {
	count := 1
	for _, child := range n.next {
		if child != nil {
			count += countNodes(child)
		}
	}
	return count
}

func main() {
	stations := []string{
		"salempur", "salem", "satna", "sangli", "surat", "sealdah", "secunderabad", "shimla", "siliguri", "solapur",
		"patna", "pune", "puri", "purna", "palghar", "panvel", "pathankot",
		"kalyan", "kalka", "katni", "kota", "kollam",
		"delhi", "delhi cantt", "delhi sarai rohilla", "new delhi",
	}
	var trie Trie
	letters := 0
	for _, name := range stations {
		trie.Insert(name)
		letters += len(name)
	}
	fmt.Printf("%d names, %d characters, %d nodes below the root\n\n", len(stations), letters, countNodes(&trie.root)-1)
	fmt.Println("typed            a station?   starts a name?")
	for _, typed := range []string{"s", "sal", "sale", "salem", "salemp", "salempur", "delhi", "delhi c", "delhi cantt", "new", "pat", "sx"} {
		station, prefix := "no", "no"
		if trie.Search(typed) {
			station = "yes"
		}
		if trie.StartsWith(typed) {
			prefix = "yes"
		}
		fmt.Printf("%-16s %-12s %s\n", "'"+typed+"'", station, prefix)
	}
}

Build and run all three · compiled/trie_session.py

from session import run, versions

# Trie.java runs as a single source file, trie.cpp is built with the sanitizers on, and go run builds trie.go.
versions("java -version", "clang++ --version", "go version")
run("""
java Trie.java
clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined trie.cpp -o trie && ./trie
go run trie.go
""")

# openjdk version "25.0.4.1" LTS
# Apple clang version 21.0.0 (clang-2100.3.34.2)
# go version go1.27.1 darwin/arm64
$ java Trie.java
26 names, 179 characters, 131 nodes below the root

typed            a station?   starts a name?
's'              no           yes
'sal'            no           yes
'sale'           no           yes
'salem'          yes          yes
'salemp'         no           yes
'salempur'       yes          yes
'delhi'          yes          yes
'delhi c'        no           yes
'delhi cantt'    yes          yes
'new'            no           yes
'pat'            no           yes
'sx'             no           no
$ clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined trie.cpp -o trie && ./trie
26 names, 179 characters, 131 nodes below the root

typed            a station?   starts a name?
's'              no           yes
'sal'            no           yes
'sale'           no           yes
'salem'          yes          yes
'salemp'         no           yes
'salempur'       yes          yes
'delhi'          yes          yes
'delhi c'        no           yes
'delhi cantt'    yes          yes
'new'            no           yes
'pat'            no           yes
'sx'             no           no
$ go run trie.go
26 names, 179 characters, 131 nodes below the root

typed            a station?   starts a name?
's'              no           yes
'sal'            no           yes
'sale'           no           yes
'salem'          yes          yes
'salemp'         no           yes
'salempur'       yes          yes
'delhi'          yes          yes
'delhi c'        no           yes
'delhi cantt'    yes          yes
'new'            no           yes
'pat'            no           yes
'sx'             no           no

C++ · compiled/children.cpp

// The station trie two ways in C++: an array of 27 child indices per node, or an unordered_map of children per node.
// It counts the bytes each one holds on the heap and times startsWith on the same calls.
#include <algorithm>
#include <array>
#include <chrono>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <new>
#include <set>
#include <string>
#include <unordered_map>
#include <vector>

// Every allocation goes through these two functions, which keep a count of the bytes in use.
static std::size_t g_in_use = 0;
void* operator new(std::size_t size) {
    auto* block = static_cast<std::size_t*>(std::malloc(size + 16));  // 16 extra bytes in front remember the size
    if (block == nullptr) throw std::bad_alloc();
    *block = size;
    g_in_use += size;
    return reinterpret_cast<char*>(block) + 16;
}
void operator delete(void* p) noexcept {
    if (p == nullptr) return;
    auto* block = reinterpret_cast<std::size_t*>(static_cast<char*>(p) - 16);
    g_in_use -= *block;
    std::free(block);
}
void operator delete(void* p, std::size_t) noexcept { operator delete(p); }

static int slot(char c) { return c == ' ' ? 26 : c - 'a'; }

static std::string with_commas(std::size_t n) {  // 39899 -> "39,899"
    std::string digits = std::to_string(n), out;
    for (std::size_t i = 0; i < digits.size(); ++i) {
        if (i > 0 && (digits.size() - i) % 3 == 0) out += ',';
        out += digits[i];
    }
    return out;
}

struct ArrayTrie {
    std::vector<std::array<int, 27>> next{1};  // node 0 is the root; a child index of 0 means "no child"
    std::vector<char> is_word = std::vector<char>(1, 0);
    void insert(const std::string& word) {
        int node = 0;
        for (char c : word) {
            int child = next[node][slot(c)];
            if (child == 0) {
                child = static_cast<int>(next.size());
                next.emplace_back();
                is_word.push_back(0);
                next[node][slot(c)] = child;
            }
            node = child;
        }
        is_word[node] = 1;
    }
    bool startsWith(const std::string& prefix) const {
        int node = 0;
        for (char c : prefix) {
            node = next[node][slot(c)];
            if (node == 0) return false;
        }
        return true;
    }
};

struct MapTrie {
    std::vector<std::unordered_map<char, int>> next{1};  // only the children that exist
    std::vector<char> is_word = std::vector<char>(1, 0);
    void insert(const std::string& word) {
        int node = 0;
        for (char c : word) {
            auto found = next[node].find(c);
            int child;
            if (found == next[node].end()) {
                child = static_cast<int>(next.size());
                next.emplace_back();
                is_word.push_back(0);
                next[node].emplace(c, child);
            } else {
                child = found->second;
            }
            node = child;
        }
        is_word[node] = 1;
    }
    bool startsWith(const std::string& prefix) const {
        int node = 0;
        for (char c : prefix) {
            auto found = next[node].find(c);
            if (found == next[node].end()) return false;
            node = found->second;
        }
        return true;
    }
};

template <class Trie>
Trie build(const std::vector<std::string>& names, std::size_t& bytes) {
    std::size_t before = g_in_use;
    Trie trie;
    for (const auto& name : names) trie.insert(name);
    trie.next.shrink_to_fit();  // drop the spare room the vectors kept for growth
    trie.is_word.shrink_to_fit();
    bytes = g_in_use - before;
    return trie;
}

template <class Trie>
double seconds(const Trie& trie, const std::vector<std::string>& calls, std::size_t& found) {
    auto start = std::chrono::steady_clock::now();
    found = 0;
    for (const auto& prefix : calls) found += trie.startsWith(prefix);
    return std::chrono::duration<double>(std::chrono::steady_clock::now() - start).count();
}

int main() {
    const char* first[] = {"ram", "shiv", "hari", "krishna", "lakshmi", "ganga", "chandra", "sundar", "dev", "raj",
        "kamal", "anand", "vijay", "nand", "mohan", "gopal", "keshav", "madhav", "narayan", "prem", "bhim", "arjun",
        "indra", "surya", "sita", "radha", "shanti", "kali", "durga", "uma", "jay", "vir", "bal", "kesh", "man",
        "sar", "dhar", "kris", "pal", "sur"};
    const char* second[] = {"pur", "nagar", "garh", "abad", "gaon", "wadi", "pada", "ganj", "kot", "pet", "palli",
        "puram", "halli", "ur", "wada", "ner", "khed", "ghat", "kund", "sar", "bag", "pura", "patti", "kheda", "dih"};
    const char* ending[] = {"", " road", " junction", " city", " town", " halt", " cantt", " east", " west"};
    std::set<std::string> unique;
    for (auto f : first)
        for (auto s : second)
            for (auto e : ending) unique.insert(std::string(f) + s + e);
    std::vector<std::string> names(unique.begin(), unique.end());

    // 200,000 calls: prefixes of names picked by a fixed sequence, a third of them with a changed last letter.
    std::vector<std::string> calls;
    std::uint64_t x = 7;
    for (int i = 0; i < 200000; ++i) {
        x = x * 6364136223846793005ULL + 1442695040888963407ULL;
        const std::string& name = names[(x >> 33) % names.size()];
        std::string prefix = name.substr(0, 1 + (x >> 13) % name.size());
        if ((x >> 7) % 3 == 0) prefix.back() = static_cast<char>('a' + (x >> 40) % 26);
        calls.push_back(prefix);
    }

    std::size_t array_bytes = 0, map_bytes = 0;
    ArrayTrie array_trie = build<ArrayTrie>(names, array_bytes);
    MapTrie map_trie = build<MapTrie>(names, map_bytes);
    std::size_t nodes = array_trie.next.size();
    std::printf("%s made-up station names, %s trie nodes below the root\n\n", with_commas(names.size()).c_str(), with_commas(nodes - 1).c_str());
    std::printf("Memory held on the heap, counted by this program's operator new:\n");
    std::printf("  trie, an array of 27 child indices per node  %5.2f MB  %4.0f bytes a node\n", array_bytes / 1e6, double(array_bytes) / nodes);
    std::printf("  trie, an unordered_map of children per node  %5.2f MB  %4.0f bytes a node\n", map_bytes / 1e6, double(map_bytes) / nodes);

    // The two take turns, 25 rounds each, and each keeps its fastest round.
    double best_array = 1e9, best_map = 1e9;
    std::size_t found_array = 0, found_map = 0;
    for (int round = 0; round < 25; ++round) {
        best_array = std::min(best_array, seconds(array_trie, calls, found_array));
        best_map = std::min(best_map, seconds(map_trie, calls, found_map));
    }
    std::printf("\nTime for one startsWith call, the fastest of 25 rounds of %s calls:\n", with_commas(calls.size()).c_str());
    std::printf("  trie, an array of 27 child indices per node  %5.1f ns  (%s found)\n", best_array / calls.size() * 1e9, with_commas(found_array).c_str());
    std::printf("  trie, an unordered_map of children per node  %5.1f ns  (%s found)\n", best_map / calls.size() * 1e9, with_commas(found_map).c_str());
}

Build and run · compiled/children_session.py

from session import run, versions

# Built with -O2 and without the sanitizers, which slow every memory access down and would distort the times.
versions("clang++ --version")
run("""
clang++ -std=c++23 -O2 -Wall -Wextra children.cpp -o children && ./children
""")

# Apple clang version 21.0.0 (clang-2100.3.34.2)
$ clang++ -std=c++23 -O2 -Wall -Wextra children.cpp -o children && ./children
9,000 made-up station names, 39,899 trie nodes below the root

Memory held on the heap, counted by this program's operator new:
  trie, an array of 27 child indices per node   4.35 MB   109 bytes a node
  trie, an unordered_map of children per node   3.18 MB    80 bytes a node

Time for one startsWith call, the fastest of 25 rounds of 200,000 calls:
  trie, an array of 27 child indices per node   40.0 ns  (143,306 found)
  trie, an unordered_map of children per node  218.3 ns  (143,306 found)