Binary Tree path sum - find if there are two with same value - use recursive function, Dictionary and LINQ

binaryTreePathSumFindSame1.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace PathSumDuplicateChecking
{
    /*Problem:
        Write a function that given a tree, returns true if at least 2 paths down the tree have the same sum. 
     *  A path is a series of nodes from the root to the leaf.  
     */
// ex1:
//     2
//   / \
//   4   5
//  / 
// 1
// returns true // 2+4+1 = 2+5
// ex2:
//     3
//   /
//   4
//  / \
// 1   1
// returns true //3+4+1 = 3+4+1
// ex3:
//   1
//  / \
// 3   4
// returns false // 1+3 != 1+4

    /*
     * Design is based on the following two blogs:
     * 1. http://www.geeksforgeeks.org/lowest-common-ancestor-binary-tree-set-1/
     * 2. http://juliachencoding.blogspot.ca/2016/04/leetcode-236-lowest-common-ancestor-in.html
     * 3. http://juliachencoding.blogspot.ca/2016/04/leetcode-236-lowest-common-ancestor-in.html
     */
    class Tree
    {
        public Tree left, right;
        public int val;

        public Tree(int v)
        {
            val = v;
            left = null;
            right = null; 
        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            bool test1 = testCase1();
            bool test2 = testCase2();
            bool test3 = testCase3(); 
        }

        // should return true
        public static bool testCase1()
        {
            Tree root = new Tree(3);
            root.left = new Tree(4);
            root.left.left = new Tree(1);
            root.left.right = new Tree(1);

            return checkPathSum(root);
        }

        // should return false 
        public static bool testCase2()
        {
            Tree root = new Tree(1);
            root.left = new Tree(3);
            root.right = new Tree(4);            

            return checkPathSum(root);
        }

        // should return true
        public static bool testCase3()
        {
            Tree root = new Tree(1);
            root.left = new Tree(3);
            root.right = new Tree(4);
            root.left.left = new Tree(5);
            root.left.right = new Tree(1); 

            return checkPathSum(root);
        }


        /*
         * The idea is to construct the dictionary to contain all path sum 
         * - once the leaf node is reached, a new entry is added to dictionary. (but add twice)
         * - update count if the key exists. 
         * 
         * Go through the LINQ learning process: 
         * 
         * 1. http://stackoverflow.com/questions/2444033/get-dictionary-key-by-value
         * 2. https://msdn.microsoft.com/en-us/library/bb340482(v=vs.110).aspx
         * 
         * 3. http://stackoverflow.com/questions/15741674/how-to-find-key-value-pair-in-a-dictionary-with-values-0-with-key-matching-a-c
             
         */
        public static bool checkPathSum(Tree root)
        {
            if (root == null)
                return false;

            Dictionary<int, int> sumTable = new Dictionary<int, int>();

            int sum = root.val;            
            
            pathSumTracking(root.left, sum, sumTable);                             
            
            pathSumTracking(root.right, sum, sumTable);                                

            // check sumTable and see if there is any key with value more than 1. // wrong!          
            // check sumTable and see if there is any key with value more than 2. One path sum is added twice. 
            
            int count = sumTable.Where(r =>  r.Value > 2).Count();  // 2 not 1, one path sum is added twice 
           
            if (count > 0)
                return true;
            else
                return false; 
        }

        /*
         * one leaf node will invoke left and right child to call pathSumTracking, 
         * both are null, and then, both are added to Dictionary. 
         * So, one path sum will be counted twice in the dictionary; 
         * 
         * For duplicate path sum, if there are 2 path sum with same value, then dictionary contains value 4 for
         * the path sum
         * 
         * - Can be better - 
         * 1. Do not assume that each path sum is added to dictionary once - Debugging and then find the design issue. 
         * 2. The code is more clean with no if statement, with some compromise. 
         */
        public static void pathSumTracking(Tree root, int sum, Dictionary<int, int> dict)
        {
            if (root == null)
            {
                if (dict.ContainsKey(sum))
                {                   
                    dict[sum] += 1;
                }
                else
                {
                    dict.Add(sum, 1); 
                }

                return; 
            }

            int addValue = sum + root.val;
            pathSumTracking(root.left,  addValue, dict); // check the count 
            pathSumTracking(root.right, addValue, dict); 
        }
    }
}