Lexicon

A Java implementation of a lexicon (dictionary) backed by a trie — a recursive, letter-tree data structure that efficiently stores and retrieves strings. Each path from root to a marked node traces out a word; each intermediate node represents a valid prefix.

What Is a Trie?

A trie (also called a prefix tree) is a tree where each node represents a single character. Words are stored by chaining characters from root to leaf. Because all words sharing a prefix share the same path, tries excel at prefix-based lookups — querying whether "app" is a prefix of any stored word takes O(k) time where k is the length of the query string, regardless of how many words are in the lexicon.

         (root)
        /      \
       a        b
      / \        \
     p   r        e
     |   |        |
     p   t       [d]
     |   |
    [e] [s]
    
 Words: "appe", "arts", "bed"
 Brackets denote word-ending nodes.

Features

• add(String word) — inserts a word into the trie, creating nodes as needed
• contains(String word) — returns true if the exact word is in the lexicon
• containsPrefix(String prefix) — returns true if any stored word begins with the given prefix
• iterator() — returns an iterator over all words in the lexicon in alphabetical order (depth-first traversal)
• size() — returns the number of words stored

Implementation Details

Recursive node structure — Each TrieNode holds an array of 26 child pointers (one per letter) and a boolean flag marking whether it terminates a valid word. Insert and lookup operations recurse on the remaining suffix at each level.

Prefix pruning — containsPrefix can short-circuit as soon as a null child pointer is encountered, making it highly efficient for use cases like the Boggle board solver (where knowing a prefix is invalid lets you abandon entire search branches early).

Alphabetical iteration — Because children are stored in fixed alphabetical order (a=0, b=1, ...), an in-order DFS naturally yields all words sorted lexicographically without any additional sorting step.

Time complexity — All core operations run in O(k) where k is the length of the input string, independent of the number of words stored. This outperforms a hash set for prefix queries and outperforms a sorted array for insertions.

Project Structure

Lexicon/
└── src/
    ├── Lexicon.java        # Interface defining the lexicon contract
    ├── TrieLexicon.java    # Trie-based implementation of the Lexicon interface
    └── LexiconNode.java    # Recursive trie node (character + children + isWord flag)

Note: class names may vary — verify against the actual source files.

Running

Compile from the src/ directory:

javac *.java

The TrieLexicon can be loaded with any newline-delimited word file:

Lexicon lex = new TrieLexicon();
lex.addWordsFromFile("words.txt");

System.out.println(lex.contains("hello"));        // true
System.out.println(lex.containsPrefix("hel"));    // true
System.out.println(lex.size());                   // number of words loaded

Built With

• Java