Implement Trie (Prefix Tree)

Each node holds up to 26 children and an end-of-word flag. Insert, search and startsWith all walk one child per letter.

The idea

A trie stores words letter by letter along paths from the root, so words with the same prefix share their first nodes. Inserting walks the path, creating any missing child, and marks the last node as the end of a word. Search and startsWith both walk the same path with Find; they differ only at the end: startsWith is satisfied by reaching the node at all, while search also needs that node to be marked as a word end.

Code

public class Trie {
    class Node { public Node[] Next = new Node[26]; public bool End; }
    readonly Node root = new();

    public void Insert(string word) {
        var cur = root;
        foreach (char c in word) {
            if (cur.Next[c - 'a'] == null) cur.Next[c - 'a'] = new Node();
            cur = cur.Next[c - 'a'];
        }
        cur.End = true; // a whole word ends here
    }

    public bool Search(string word) => Find(word)?.End == true;
    public bool StartsWith(string prefix) => Find(prefix) != null;

    Node Find(string s) {
        var cur = root;
        foreach (char c in s) {
            cur = cur.Next[c - 'a'];
            if (cur == null) return null; // nothing was inserted with this letter here
        }
        return cur;
    }
}

Tips

• search("ca") is false even though "car" was inserted: the path exists, but the node for a is not marked as a word end (no ring).
• Prefixes are shared: inserting "card" after "car" adds only the one node d.
• An array of 26 children gives O(1) child lookup; a Dictionary<char, Node> uses less memory when the alphabet is large or sparse.

In the .NET library

Find(word)?.End == true uses the null-conditional operator: if Find returns null, the whole expression is null, and null == true is false.