Trie implementations in C#

PrefixTrieNode.cs

public class PrefixTrieNode<TValue> where TValue : class
{
    private readonly StringComparison _strCmp = StringComparison.OrdinalIgnoreCase;

    public PrefixTrieNode(string prefix)
    {
        Prefix = prefix;
        Children = new SortedList<string, PrefixTrieNode<TValue>>(StringComparer.FromComparison(_strCmp));
    }

    public string Prefix { get; }

    public TValue Value { get; private set; }

    public SortedList<string, PrefixTrieNode<TValue>> Children { get; }

    public int Count { get; private set; }

    public bool TryGetValue(string searchPrefix, out TValue value)
    {
        // Key is exact or our prefix matches and we have no children, return value on this node
        if (Prefix.Equals(searchPrefix, _strCmp)
            || (Children.Count == 0 && Prefix.StartsWith(searchPrefix)))
        {
            value = Value;
            return value == null;
        }

        // Otherwise look deeper at children, there should only be one child with a common prefix
        foreach (KeyValuePair<string, PrefixTrieNode<TValue>> child in Children)
        {
            if (child.Value.TryGetValue(searchPrefix, out value))
            {
                return true;
            }
        }

        // The search prefix didn't match anything
        value = null;
        return false;
    }

    public void Insert(string key, TValue value)
    {
        if (key is null)
        {
            throw new ArgumentNullException(nameof(key));
        }

        if (!key.StartsWith(Prefix, _strCmp))
        {
            throw new InvalidOperationException($"Key '{key}' does not match prefix '{Prefix}' and cannot be inserted");
        }

        if (key.Equals(Prefix, _strCmp))
        {
            if (Value is not null)
            {
                throw new InvalidOperationException($"Cannot have duplicate entries for key '{key}'");
            }

            Count++;
            Value = value;
            return;
        }

        int nextCharIdx = Prefix.Length;
        char nextChar = key[nextCharIdx];

        int childIndex = -1;
        for (int i = 0; i < Children.Count; i++)
        {
            // Another child with a common prefix
            if (AreCharsEqual(Children.Keys[i][nextCharIdx], nextChar))
            {
                childIndex = i;
                break;
            }
        }

        // No other child found with a longer common prefix,
        // just insert as a new child
        if (childIndex == -1)
        {
            Children[key] = new PrefixTrieNode<TValue>(key){ Value = value };
            Count++;
            return;
        }

        PrefixTrieNode<TValue> longerPrefixValue = Children.Values[childIndex];

        // If the other node strictly encompasses our key, just insert there
        if (key.StartsWith(longerPrefixValue.Prefix, _strCmp))
        {
            longerPrefixValue.Insert(key, value);
            Count++;
            return;
        }

        // Otherwise, there's some shared prefix of the two nodes and we need to put them beneath a new common prefix
        Children.Remove(longerPrefixValue.Prefix);
        string commonPrefix = GetCommonPrefix(key, longerPrefixValue.Prefix, Prefix.Length);
        Children[commonPrefix] = new PrefixTrieNode<TValue>(commonPrefix)
        {
            Children = {
                [key] = new PrefixTrieNode<TValue>(key){ Value = value },
                [longerPrefixValue.Prefix] = longerPrefixValue,
            },
        };
        Count++;
    }

    private string GetCommonPrefix(string s1, string s2, int start)
    {
        int i = start;
        while (i < s1.Length && i < s2.Length)
        {
            if (!AreCharsEqual(s1[i], s2[i]))
            {
                break;
            }

            i++;
        }

        return s1.Substring(0, i);
    }

    private bool AreCharsEqual(char c1, char c2) =>
        _strCmp switch
        {
            StringComparison.Ordinal => c1 == c2,
            StringComparison.OrdinalIgnoreCase => char.ToUpper(c1) == char.ToUpper(c2),
            StringComparison.InvariantCultureIgnoreCase => char.ToUpperInvariant(c1) == char.ToUpperInvariant(c2),
            _ => throw new NotImplementedException(),
        };
}

Trie.cs

public class Trie<TKey, TValue>
{
    private readonly Dictionary<TKey, TrieNode> _children;

    public Trie()
    {
        _children = new Dictionary<TKey, TrieNode>();
    }

    public bool TryGetValue(ReadOnlySpan<TKey> key, out TValue value)
    {
        if (key.Length == 0)
        {
            throw new ArgumentException($"Key cannot be empty");
        }

        if (_children.TryGetValue(key[0], out TrieNode node))
        {
            return node.TryGetValue(key.Slice(1), out value);
        }

        value = default;
        return false;
    }

    public void Insert(ReadOnlySpan<TKey> key, TValue value)
    {
        if (key.Length == 0)
        {
            throw new ArgumentException($"Key cannot be empty");
        }

        if (!_children.TryGetValue(key[0], out TrieNode node))
        {
            node = new TrieNode(key[0]);
            _children[key[0]] = node;
        }

        node.Insert(key.Slice(1), value);
    }

    private class TrieNode
    {
        public TrieNode(TKey key)
            : this(parent: null, key)
        {
        }

        public TrieNode(TrieNode parent, TKey key)
        {
            Key = key;
            Children = new Dictionary<TKey, TrieNode>();
        }

        public TKey Key { get; }

        public TValue Value { get; set; }

        public TrieNode Parent { get; }

        public Dictionary<TKey, TrieNode> Children { get; }

        public bool TryGetValue(ReadOnlySpan<TKey> key, out TValue value)
        {
            if (key.Length == 0)
            {
                if (Value is null)
                {
                    value = default;
                    return false;
                }

                value = Value;
                return true;
            }

            TKey next = key[0];

            if (Children.TryGetValue(next, out TrieNode nextNode))
            {
                return nextNode.TryGetValue(key.Slice(1), out value);
            }

            value = default;
            return false;
        }

        public void Insert(ReadOnlySpan<TKey> key, TValue value)
        {
            if (key.Length == 0)
            {
                if (Value is not null)
                {
                    throw new InvalidOperationException($"Cannot add duplicate key");
                }

                Value = value;
                return;
            }

            if (!Children.TryGetValue(key[0], out TrieNode child))
            {
                child = new TrieNode(this, key[0]);
                Children[key[0]] = child;
            }

            child.Insert(key.Slice(1), value);
        }

        public TKey[] GetPath()
        {
            var list = new List<TKey>();
            TrieNode current = this;
            do
            {
                list.Add(current.Key);
                current = current.Parent;
            } while (current is not null);

            list.Reverse();
            return list.ToArray();
        }
    }
}