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>();
 }
 }
}

• Gilad: @wolfy no you can't. Why is it better? Maybe I can create a singleton or something close to it.
• Pieter Witvoet: @Wolfy: C# is a managed language, so I'm not sure what you're getting at?
• Wolfy: @PieterWitvoet ahh okay then nevermind, sorry I never used C# before...

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.