🎓 A1Learner
🔍

DSA Tries

A trie is a tree where each node holds a map of next letters and a flag for word ends. A word is the path spelled by following its letters from the root.

One word as a path

Inserting cat makes one child link per letter. Only the final node carries the word-end flag.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False


root = TrieNode()
node = root
for letter in "cat":
    node.children[letter] = TrieNode()
    node = node.children[letter]
node.is_end = True
print("Root children:", list(root.children.keys()))
print("After c:", list(root.children["c"].children.keys()))
print("After a:", list(root.children["c"].children["a"].children.keys()))
print("End flag at t:", node.is_end)
print("End flag at a:", root.children["c"].children["a"].is_end)

Shared prefixes share nodes

The words cat and car share their first two letters. Their paths share those nodes and split only at the last letter.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

def insert(root, word):
    node = root
    for letter in word:
        if letter not in node.children:
            node.children[letter] = TrieNode()
        node = node.children[letter]
    node.is_end = True


def count_nodes(node):
    total = 1
    for child in node.children.values():
        total += count_nodes(child)
    return total


root = TrieNode()
insert(root, "cat")
insert(root, "car")
print("Nodes for cat and car:", count_nodes(root))
print("Letters if stored apart:", 3 + 3)
print("Children of a:", sorted(root.children["c"].children["a"].children.keys()))

Example

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

def insert(root, word):
    node = root
    for letter in word:
        if letter not in node.children:
            node.children[letter] = TrieNode()
        node = node.children[letter]
    node.is_end = True


def walk(root, text):
    node = root
    for letter in text:
        if letter not in node.children:
            return None
        node = node.children[letter]
    return node


def search(root, word):
    node = walk(root, word)
    return node is not None and node.is_end


def starts_with(root, prefix):
    return walk(root, prefix) is not None


def count_nodes(node):
    total = 1
    for child in node.children.values():
        total += count_nodes(child)
    return total


root = TrieNode()
for word in ["cat", "car", "card", "dog"]:
    insert(root, word)
print("Nodes in trie:", count_nodes(root))
for word in ["cat", "car", "ca", "card", "do"]:
    print(f"Search {word}: {search(root, word)}")
for prefix in ["ca", "car", "do", "x"]:
    print(f"StartsWith {prefix}: {starts_with(root, prefix)}")

Key points

  • Trie node: a dict of letters to child nodes, plus one word-end flag
  • Each edge adds one letter, so a path from the root spells a string
  • A prefix is the opening part of a word, and it is a path that stops early
  • Words that share a prefix share the opening nodes of their paths
  • Search needs the word-end flag, while a prefix check needs only the path

In this example, four words are inserted into one trie. The node count is nine, below the thirteen letters the words hold in total. Search finds cat, car and card, but reports ca and do as missing. The prefix checks accept ca, car and do, because those paths exist even without a word-end flag.

Note

The root holds no letter, and it spells the empty prefix

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

Search for ca returns False while startsWith ca returns True. Why?