Blind 75Medium

Implement Trie — Prefix Tree Operations

Build a node structure with child maps and an isWord flag to support insert, search, and prefix queries in O(L).

TriePrefix Tree

View problem on LeetCode

Problem Statement

Implement the Trie (Prefix Tree) data structure with insert, search, and startsWith operations.

Why This Problem Matters

Concrete application of trie concepts to string dictionaries.
Demonstrates trade-offs between arrays and hash maps for child pointers.
Provides reusable code for autocomplete, word search, and compression problems.

Thought Process

Design node representation

Each node stores child references and a boolean indicating word completion.

Traverse characters sequentially

Insert and search iterate over characters, creating nodes on demand.

Differentiate full word vs prefix

isWord flag ensures search distinguishes between complete words and prefixes.

Step-by-Step Reasoning

Define Node with children map and isWord flag.
Insert: iterate characters, creating children via computeIfAbsent; mark final node.
Search: traverse, returning false when a child is missing; return node.isWord.
startsWith: same as search but return true as long as traversal succeeds.

Dry Run

Insert "apple" then search "apple" and "app"

search("apple") true, search("app") false, startsWith("app") true.

Insert "app" then "apple"

Tree shares prefix nodes, demonstrating memory reuse.

Complexity Analysis

Time

O(L)

Space

O(AL)

Why

Operations depend on word length L and alphabet size A.

Annotated Solution

JAVA

import java.util.HashMap;
import java.util.Map;

public class Trie {
  private final Node root = new Node();

  public void insert(String word) {
    Node current = root;
    for (char c : word.toCharArray()) {
      current = current.children.computeIfAbsent(c, key -> new Node());
    }
    current.isWord = true;
  }

  public boolean search(String word) {
    Node node = traverse(word);
    return node != null && node.isWord;
  }

  public boolean startsWith(String prefix) {
    return traverse(prefix) != null;
  }

  private Node traverse(String sequence) {
    Node current = root;
    for (char c : sequence.toCharArray()) {
      current = current.children.get(c);
      if (current == null) {
        return null;
      }
    }
    return current;
  }

  private static class Node {
    Map<Character, Node> children = new HashMap<>();
    boolean isWord;
  }
}

HashMap-based children keep the implementation concise and flexible, supporting any character set.

Common Pitfalls

Returning true for search when only the prefix exists fails to respect isWord flag.
Using arrays sized for lowercase letters fails with uppercase or arbitrary characters.
Not initialising root properly leads to NullPointerException on first insert.

Follow-Up Questions

How do you support delete with cleanup of orphan nodes?
Can you augment nodes with counts to support prefix frequency queries?

Key Takeaways

Explicit node structures make it easy to bolt on additional metadata later.

Tries balance time and space—be ready to discuss trade-offs.

Combine with DFS for multi-word board searches.