Core Structure

• Root node: An empty node serving as the entry point; its children represent the first characters of stored strings.
• Internal nodes: Represent intermediate characters in strings.
• Leaf nodes: Mark the end of a valid word via a boolean flag, evenif they have children (e.g., "do" and "dog" can coexist).

Basic Implementation

We begin by defining a node that supports 26 lowercase English letters:

class TrieNode {
    private static final int ALPHABET_SIZE = 26;
    TrieNode[] branches = new TrieNode[ALPHABET_SIZE];
    boolean isTerminal;

    TrieNode() {
        isTerminal = false;
        for (int i = 0; i < ALPHABET_SIZE; i++) {
            branches[i] = null;
        }
    }
}

The trie class manages the root and provides core operations:

public class Trie {
    private TrieNode head;

    public Trie() {
        head = new TrieNode();
    }

    public void add(String word) {
        TrieNode current = head;
        for (char c : word.toCharArray()) {
            int position = c - 'a';
            if (current.branches[position] == null) {
                current.branches[position] = new TrieNode();
            }
            current = current.branches[position];
        }
        current.isTerminal = true;
    }

    public boolean contains(String word) {
        TrieNode current = head;
        for (char c : word.toCharArray()) {
            int position = c - 'a';
            if (current.branches[position] == null) {
                return false;
            }
            current = current.branches[position];
        }
        return current != null && current.isTerminal;
    }
}

Extending Functionality

To support deletion, we recursively traverse the path and remove nodes only if they are unused by other words:

public boolean remove(String word) {
    return remove(head, word, 0);
}

private boolean remove(TrieNode node, String word, int depth) {
    if (node == null) return false;

    if (depth == word.length()) {
        if (!node.isTerminal) return false;
        node.isTerminal = false;
        return isEmpty(node);
    }

    int idx = word.charAt(depth) - 'a';
    boolean shouldRemove = remove(node.branches[idx], word, depth + 1);

    if (shouldRemove) {
        node.branches[idx] = null;
        return isEmpty(node) && !node.isTerminal;
    }

    return false;
}

private boolean isEmpty(TrieNode node) {
    for (TrieNode child : node.branches) {
        if (child != null) return false;
    }
    return true;
}

To list all words with a given prefix, we first locate the prefix node, then perform a depth-first traversal:

public void listWordsWithPrefix(String prefix) {
    TrieNode node = findNode(prefix);
    if (node == null) {
        System.out.println("No matches found.");
        return;
    }
    listWords(node, prefix);
}

private void listWords(TrieNode node, String prefix) {
    if (node.isTerminal) {
        System.out.println(prefix);
    }

    for (int i = 0; i < 26; i++) {
        if (node.branches[i] != null) {
            char nextChar = (char)('a' + i);
            listWords(node.branches[i], prefix + nextChar);
        }
    }
}

private TrieNode findNode(String prefix) {
    TrieNode current = head;
    for (char c : prefix.toCharArray()) {
        int idx = c - 'a';
        if (current.branches[idx] == null) return null;
        current = current.branches[idx];
    }
    return current;
}

Application: Student Grade Manager

While tries efficiently store and search names, they are not inherently designed for value updates. To handle grades, we combine the trie with a hash map for O(1) access to associated data:

import java.util.HashMap;

public class StudentGradeSystem {
    private Trie nameIndex;
    private HashMap<String, Integer> gradeMap;

    public StudentGradeSystem() {
        nameIndex = new Trie();
        gradeMap = new HashMap<>();
    }

    public void register(String name, int grade) {
        nameIndex.add(name);
        gradeMap.put(name, grade);
    }

    public void updateGrade(String name, int newGrade) {
        if (!gradeMap.containsKey(name)) {
            throw new IllegalArgumentException("Student not registered.");
        }
        gradeMap.put(name, newGrade);
    }

    public void deregister(String name) {
        if (gradeMap.containsKey(name)) {
            gradeMap.remove(name);
            // Note: Trie node deletion omitted for simplicity
        } else {
            throw new IllegalArgumentException("Student not found.");
        }
    }

    public int getGrade(String name) {
        Integer grade = gradeMap.get(name);
        if (grade == null) {
            throw new IllegalArgumentException("Student not registered.");
        }
        return grade;
    }

    public boolean hasStudent(String name) {
        return nameIndex.contains(name);
    }
}

Usage example:

public static void main(String[] args) {
    StudentGradeSystem system = new StudentGradeSystem();
    system.register("alice", 90);
    system.register("bob", 85);
    system.register("charlie", 92);

    System.out.println(system.hasStudent("alice"));     // true
    System.out.println(system.getGrade("bob"));         // 85
    system.updateGrade("charlie", 98);
    System.out.println(system.getGrade("charlie"));     // 98
    system.deregister("bob");
    System.out.println(system.hasStudent("bob"));       // false
}

While this approach separates storage concerns for efficiency, it leaves orphaned trie nodes after deletions. For full consistency, the trie must be updated to prune unused branches — a trade-off between memory usage and operational complexity.