public class Trie
    {
        private TrieNode RootNode { get; set; }

        public Trie()
        {
            RootNode = new TrieNode('^', 0, null);

        }

        public void Insert(string s)
        {
            var commonPrefix = GetPrefix(s);
            var current = commonPrefix;

            for (var i = current.Depth; i < s.Length; i++)
            {
                var newNode = new TrieNode(s[i], current.Depth + 1, current);
                current.ChildNodes.Add(newNode);
                current = newNode;
            }

            current.ChildNodes.Add(new TrieNode('$', current.Depth + 1, current));
        }

        public TrieNode GetPrefix(string word)
        {
            var current = RootNode;
            var result = current;

            foreach (char c in word)
            {
                current = current.FindChildNode(c);
                if (current == null)
                {
                    break;
                }
                result = current;
            }
            return result;
        }
    }
public class TrieNode
{
    private char Value { get; set; }
    public List<TrieNode> ChildNodes { get; set; }
    private TrieNode Parent { get; set; }
    public int Depth { get; set; }

    public TrieNode( char value, int depth, TrieNode parent)
    {
        ChildNodes = new List<TrieNode>();
        Parent = parent;
        Value = value;
        Depth = depth;
    }

    public bool IsLeaf()
    {
        return ChildNodes.Any();
    }

    public TrieNode FindChildNode(char c)
    {
        TrieNode node = null;

        foreach (var variable in ChildNodes)
        {
            if (variable.Value == c)
            {
                return variable;
            }

        }
        return node;
    }
}