Insert and Search a Word in a Trie

Follow the letters that exist, create the ones that do not, and mark the last.

Inserting a word into a trie and searching for one both walk down from the root, one letter per step; they differ only in what happens when a letter has no child. This card covers both operations by hand, on four words inserted into an empty trie and then five lookups, and the one check that separates searching for a whole word from checking a prefix.

A trie is a tree whose root holds no letter and whose every other node stands for one letter, so a word is a path from the root. A node carries an end-of-word mark when its path spells a stored word.

The rules fit in two lines. To insert, take each letter in turn: if the current node already has a child for it, follow that child; if not, create one and follow it. After the last letter, mark the node. To search, follow the children the same way, but stop with the answer no as soon as a letter has no child, because a search never creates anything.

The steps insert sun, sum, sung and sky, in that order, and show the trie after each one.

Inserting sun, sum, sung and sky into an empty trie

Insert sun: every letter is new

The root has no children, so s is created, then u below it, then n below u. n is the last letter, so it gets the mark. Three nodes were created and none was followed.

After inserting sun

root
- s
  - u
    - n, end of word: sun

Insert sum: follow two letters, create one

s and u already exist, so the walk follows them. u has a child n but no child m, so m is created beside n and marked. sum now shares its first two nodes with sun.

After inserting sum

root
- s
  - u
    - n, end of word: sun
    - m, end of word: sum

Insert sung: follow three letters, create one

s, u and n all exist and are followed. n has no child g, so g is created below it and marked. n keeps its own mark, so it now ends sun and also sits in the middle of sung.

After inserting sung

root
- s
  - u
    - n, end of word: sun
      - g, end of word: sung
    - m, end of word: sum

Insert sky: follow one letter, create two

s exists and is followed. s has a child u but no child k, so k is created, then y below it, and y is marked. The trie holds four words in seven nodes below the root.

After inserting sky

root
- s
  - u
    - n, end of word: sun
      - g, end of word: sung
    - m, end of word: sum
  - k
    - y, end of word: sky

Searching uses the finished trie. A search for sum follows s, u and m, and m is marked, so the answer is yes. A search for su follows s and u, and the path exists, but u has no mark, so the answer is no: su was never inserted. A search for sing follows s and then stops, because s has no child i.

Checking a prefix is the same walk with the mark ignored. su and sk are both present as prefixes, because their paths exist; so is not, because s has no child o.

The run below performs the same inserts and lookups and prints, for each one, whether every letter was followed or created and where a lookup stopped.

insert_search_trace.pypy

class Node:
    def __init__(self):
        self.children = {}
        self.is_word = False


def insert(root, word):
    node = root
    steps = []
    for letter in word:
        if letter in node.children:
            steps.append(f"follow {letter}")
        else:
            node.children[letter] = Node()
            steps.append(f"create {letter}")
        node = node.children[letter]
    node.is_word = True
    print(f"insert {word}: " + ", ".join(steps) + f", mark {word[-1]} as end of word")


def walk(root, text):
    node = root
    visited = []
    for letter in text:
        if letter not in node.children:
            return None, visited + [f"no child {letter}"]
        node = node.children[letter]
        visited.append(letter)
    return node, visited


def search(root, word):
    node, visited = walk(root, word)
    found = node is not None and node.is_word
    print(f"search {word}: {' '.join(visited)} -> {found}")


def starts_with(root, prefix):
    node, visited = walk(root, prefix)
    print(f"starts_with {prefix}: {' '.join(visited)} -> {node is not None}")


root = Node()
for word in ["sun", "sum", "sung", "sky"]:
    insert(root, word)
search(root, "sum")
search(root, "su")
search(root, "sing")
starts_with(root, "su")
starts_with(root, "sk")
starts_with(root, "so")

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

insert sun: create s, create u, create n, mark n as end of word
insert sum: follow s, follow u, create m, mark m as end of word
insert sung: follow s, follow u, follow n, create g, mark g as end of word
insert sky: follow s, create k, create y, mark y as end of word
search sum: s u m -> True
search su: s u -> False
search sing: s no child i -> False
starts_with su: s u -> True
starts_with sk: s k -> True
starts_with so: s no child o -> False

Each operation took one step per letter: three for sun, four for sung, two for su, and a lookup that met a missing child stopped there. None of them looked at the other words, and that is the property the rest of the topic relies on. A trie with a million words beginning with s would have walked the same three nodes to answer whether sum was stored.

← → move through sections and cards