LeetCode: Trie Tree implementation, Search, Insert, startWith C#

Question

https://leetcode.com/problems/implement-trie-prefix-tree/

Please comment about performance and style.

Implement a trie with insert, search, and startsWith methods.

Example:

Trie trie = new Trie();

trie.insert("apple");
trie.search("apple");   // returns true
trie.search("app");     // returns false
trie.startsWith("app"); // returns true
trie.insert("app");   
trie.search("app");     // returns true

Note:

You may assume that all inputs are consist of lowercase letters a-z. All inputs are guaranteed to be non-empty strings.

using System.Collections.Generic;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace TrieQuestions
{
    /// <summary>
    /// https://leetcode.com/problems/implement-trie-prefix-tree/
    /// </summary>
    [TestClass]
    public class TrieTreeImplementation
    {
        [TestMethod]
        public void TrieInsertTest()
        {
            Trie trie = new Trie();
            trie.Insert("cat");
            Assert.IsTrue(trie.Search("cat"));
        }

        [TestMethod]
        public void TriePrefixSearchTest()
        {
            Trie trie = new Trie();
            trie.Insert("cats");
            Assert.IsTrue(trie.StartsWith("cat"));
        }

        [TestMethod]
        public void OneLetterEdgeCaseTest()
        {
            Trie trie = new Trie();
            trie.Insert("a");
            Assert.IsTrue(trie.Search("a"));
            Assert.IsTrue(trie.StartsWith("a"));
        }
    }

    public class Trie
    {
        public TrieNode Head { get; set; }

        /** Initialize your data structure here. */
        public Trie()
        {
            Head = new TrieNode();
        }

        /** Inserts a word into the trie. */
        public void Insert(string word)
        {
            var current = Head;
            for (int i = 0; i < word.Length; i++)
            {
                if (!current.Edges.ContainsKey(word[i]))
                {
                    current.Edges.Add(word[i], new TrieNode());
                }
                current = current.Edges[word[i]];
            }
            current.IsTerminal = true;
        }

        /** Returns if the word is in the trie. */
        public bool Search(string word)
        {
            var current = Head;
            for (int i = 0; i < word.Length; i++)
            {
                if (!current.Edges.ContainsKey(word[i]))
                {
                    return false;
                }
                current = current.Edges[word[i]];
            }
            return current.IsTerminal == true;
        }

        /** Returns if there is any word in the trie that starts with the given prefix. */
        public bool StartsWith(string prefix)
        {
            var current = Head;
            for (int i = 0; i < prefix.Length; i++)
            {
                if (!current.Edges.ContainsKey(prefix[i]))
                {
                    return false;
                }
                current = current.Edges[prefix[i]];
            }
            return true;
        }
    }

    public class TrieNode
    {
        public Dictionary<char, TrieNode> Edges { get; set; }
        public bool IsTerminal { get; set; }
        public TrieNode()
        {
            Edges = new Dictionary<char, TrieNode>();
        }
    }
}

Answer 1

In terms of data structures and algorithms this all looks pretty straightforward - not much to say about that.

Performance

• Edges.ContainsKey and Edges[...] each perform a lookup. Edges.TryGetValue lets you achieve the same with just a single lookup.

Design

• I see no reason why Trie.Head should be public, and certainly not why it should have a public setter. That's poor encapsulation. Likewise, TrieNode.Edges should be get-only: you don't want outside code to be able to do Edges = null;.
• Search and StartsWith do exactly the same thing, except for the final check. I'd move the duplicate code to a TrieNode FindNode(string prefix) helper method.
• TrieNode is only used internally within Trie, so it makes sense to make it a private inner class.

Other notes

• You can remove Trie's constructor if you initialize Head directly: TrieNode Head { get; } = new TrieNode();. The same goes for TrieNode and Edges.
• I'd replace those for loops with foreach loops, for clarity's sake.
• Comparing a boolean against true is unnecessary. Just do return current.IsTerminal;
• I'd replace those default LeetCode comments with C#-specific xml comments.