Leetcode: Map Sum Pairs C# Implement a MapSum class with insert, and sum methods.
  
  For the method insert, you'll be given a pair of (string, integer).
  The string represents the key and the integer represents the value. If
  the key already existed, then the original key-value pair will be
  overridden to the new one.
  
  For the method sum, you'll be given a string representing the prefix,
  and you need to return the sum of all the pairs' value whose key
  starts with the prefix.

Example 1:
Input: insert("apple", 3), Output: Null
Input: sum("ap"), Output: 3
Input: insert("app", 2), Output: Null
Input: sum("ap"), Output: 5



Please comment on performance and style

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

namespace TrieQuestions
{
    [TestClass]
    public class TrieMapSum
    {
        [TestMethod]
        public void MapSumTest()
        {
            MapSum mapSum = new MapSum();
            mapSum.Insert("apple", 3);
            Assert.AreEqual(3, mapSum.Sum("ap"));
            mapSum.Insert("app", 2);
            Assert.AreEqual(5, mapSum.Sum("ap"));
        }
    }

    public class MapSum
    {
        private TrieMSNode Head;
        /** Initialize your data structure here. */
        public MapSum()
        {
            Head = new TrieMSNode();
        }

        public void Insert(string key, int val)
        {
            var current = Head;
            foreach (var letter in key)
            {
                if (!current.Edges.ContainsKey(letter))
                {
                    current.Edges.Add(letter, new TrieMSNode());
                }
                current = current.Edges[letter];
            }

            current.IsTerminal = true;
            current.Value = val;
        }

        public int Sum(string prefix)
        {
            int sum = 0;
            var current = Head;
            foreach (var letter in prefix)
            {
                if (!current.Edges.ContainsKey(letter))
                {
                    return sum;
                }

                current = current.Edges[letter];
            }
            // we use dfs for each edges of the trie;
            return DFS(current);
        }

        private int DFS(TrieMSNode current)
        {
            if (current == null)
            {
                return 0;
            }

            int sum = current.IsTerminal ? current.Value : 0;
            foreach (var edge in current.Edges.Values)
            {
                sum += DFS(edge);
            }
            return sum;
        }
    }

    internal class TrieMSNode
    {
        public Dictionary&lt;char, TrieMSNode&gt; Edges { get; set; }
        public bool IsTerminal;
        public int Value;

        public TrieMSNode()
        {
            Edges = new Dictionary&lt;char, TrieMSNode&gt;();
            IsTerminal = false;
            Value = 0;
        }
    }
}
In Insert(...) you should use TryGetValue instead of ContainsKeyfor efficiency:

  foreach (var letter in key)
  {
    if (!current.Edges.TryGetValue(letter, out var edge))
    {
      edge = current.Edges[letter] = new TrieMSNode();
    }
    current = edge;
  }




Name your methods after what they do, not after their implementation:


  DFS(...)


could be GetSumFrom(...)




public int Sum(string prefix)
{
  int sum = 0;
  var current = Head;
  foreach (var letter in prefix)
  {
    if (!current.Edges.ContainsKey(letter))
    {
      return sum;
    }
    current = current.Edges[letter];
  }



Here the sum variable is redundant because it is never changed so you could just return 0 from the loop

Again the loop can be optimized:

  foreach (char letter in prefix)
  {
    if (!current.Edges.TryGetValue(letter, out current))
      return 0;
  }





DFS()



can be simplified using LINQ:

    private int GetSumFrom(TrieMSNode current)
{
  if (current == null)
  {
    return 0;
  }

  return current.Edges.Aggregate(current.Value, (sum, kvp) =&gt; sum + GetSumFrom(kvp.Value));
}


You really don't have to check for IsTerminal because you know that only terminal nodes have a values different from 0.

You should test this LINQ-approach against your own plain foreach-loop, and you'll maybe find the latter fastest.