At least 2 paths down the binary tree have the same sum

Question

Problem statement

Write a function that given a binary 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.

Examples:
Example 1:
  2
 / \
4 5
/
1
return true // 2 + 4 + 1 = 2 + 5

Example 2:
  3
  /
 4
/ \
1 1
return true //3+4+1 = 3+4+1

Example 3:
  1
  / \
3   4
return false // 1+3 != 1+4

Introduction of algorithm

The algorithm is very good one for me to practice write a depth first search and also start to learn LINQ. I still remembered that I did the practice in June 2016, and the code was written and saved as a gist here. I reviewed the code today, and rewrote the code to make a new base case selection for depth first search. Based on the facts that last 12 months I asked questions over 35 questions on this site and also I have practiced mock interview over 100 times since this March 2017, I have more ideas to review my own code after six months. I also learned from my mock interview experience last month missing a base case.

Code improvements

I decided to make a few improvements based on my last practice over 18 months ago. Internal class is used instead of external class. I choose to use camel case for public method, and rename the function DuplicateCheckingPathSum to make the function name self-documenting. Specially I took 10 - 20 minutes to go over those stackoverflow links to learn LINQ and also ASP.NET C# class and I found that those links are really helpful for me to warm up LINQ. It is tough for me to see that after 18 months I still do not make big progress on LINQ and the functional programming syntax still looks like foreigners to me.

Most of important change is that I learn better recursive function design after 18 months. I was surprised that I ended my last practice with so many issues. The base case should be selected to avoid duplicated count of each path. I like to see the depth first search algorithm specially a recursive function is written in very structured way, base case is very clear and also the recurrence formula afterwards.

Please share your advice on my journey to be a good thinker on depth first search on binary tree. I still make mistakes on depth first search and have interest to know how to choose the base case as an art and scientific approach.

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

namespace PathSumDuplicateChecking
{    
    /// <summary>
    /// Problem:
    /// Write a function that given a binary 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.
    /// </summary>    
    class Program
    {
        internal class Tree
        {
            public Tree Left, Right;
            public int value;

            public Tree(int number)
            {
                value = number;
                Left  = null;
                Right = null;
            }
        }

        static void Main(string[] args)
        {
            RunTestcase1();
            RunTestcase2();
            RunTestcase3();
        }

        public static void RunTestcase1()
        {
            Tree root = new Tree(3);
            root.Left = new Tree(4);
            root.Left.Left = new Tree(1);
            root.Left.Right = new Tree(1);

            Debug.Assert(DuplicateCheckingPathSum(root));
        }

        public static void RunTestcase2()
        {
            Tree root  = new Tree(1);
            root.Left  = new Tree(3);
            root.Right = new Tree(4);

            Debug.Assert(!DuplicateCheckingPathSum(root));
        }

        public static void RunTestcase3()
        {
            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);

            Debug.Assert(DuplicateCheckingPathSum(root));
        }        

        /// <summary>        
        /// Learn to use LINQ to do query. 
        /// 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
        /// </summary>
        /// <param name="root"></param>
        /// <returns></returns>
        public static bool DuplicateCheckingPathSum(Tree root)
        {
            if (root == null)
            {
                return false;
            }

            var dictionary = new Dictionary<int, int>();            

            addToPath(root, 0, dictionary);                     

            int count = dictionary.Where(r => r.Value > 1).Count();  

            return (count > 0);            
        }

        /// <summary>
        /// Choose a base case for the convenience to calculate the sum; 
        /// Orignal thought is that base case is the node with null value, but 
        /// end up add one path twice. 
        /// So I decide to choose to define the base case in a different way. 
        /// If the node is the leaf node, then depth first search has its base case. 
        /// </summary>
        /// <param name="root"></param>
        /// <param name="sum"></param>
        /// <param name="dict"></param>
        private static void addToPath(Tree root, int sum, Dictionary<int, int> dict)
        {
            var value = root.value;
            var newSum = sum + value; 

            // base case - if the node is leaf node
            if (root.Left == null && root.Right == null)
            {
                if(dict.ContainsKey(newSum))
                {
                    dict[newSum] ++; 
                }
                else 
                {
                    dict.Add(newSum, 1); 
                }
                return; 
            }            

            // recurrence                 
            if (root.Left != null)
            {
                addToPath(root.Left, newSum, dict);
            }

            if (root.Right != null)
            {
                addToPath(root.Right, newSum, dict);
            }
        }
    }
}

Answer 1

Your code is good. You perform depth first search on binary tree classically. But let me say something about it.

Problem statement is "returns true if at least 2 paths down the tree have the same sum". This means if there is any different 2 paths with same sum then true, else false

In your code, you are bypassing through the whole tree and finding sum of each path and writing this sum into dictionary, and after that you are obtaining the count of sums which appears more than one time. And result of function is (Count > 0).

1) About (Count > 0).

int count = dictionary.Where(r => r.Value > 1).Count();  
return (count > 0);

according to the statement of problem, you can write simple:

return dictionary.Any(r => r.Value > 1);

2) About using Dictionary. Do we really need it?! I don't think so. All we need is a set, there we will store founded sums. And the HashSet<T> is good and sufficient for this.

3) About bypassing through the whole tree. According to statement there is no need for it. Let say it as: if calculated sum is already in our set, then we found the answer and we can stop bypassing.

After all, code is become as (I also renamed some variables, method params and "camelized" private method name):

// I think it is better name for method
public static bool CheckForDuplicatePathSums(Tree root)
{
    if ( root == null )
    {
        return false;
    }

    //Use of HashSet<int> is sufficient 
    var setOfPathSums = new HashSet<int>();

    // flag indicating that we have found a duplicate or not
    bool duplicateFound = false;

    AddToPath(root, 0, setOfPathSums, ref duplicateFound);

    return duplicateFound;
}

private static void AddToPath(Tree node, int incomingSum, HashSet<int> pathSums, ref bool duplicateFounded)
{
    var newSum = incomingSum + node.Value;

    // base case - if the node is leaf node
    if ( node.Left == null && node.Right == null )
    {
        if ( pathSums.Contains(newSum) )
        {
            // we determined that the calculated sum is already present in our set.
            duplicateFounded = true;
        }
        else
        {
            pathSums.Add(newSum);
        }
        return;
    }

    // After we found answer, there is no more need to check the another paths
    if ( duplicateFounded )
    {
        return;
    }

    // recurrence                 
    if ( node.Left != null )
    {
        AddToPath(node.Left, newSum, pathSums, ref duplicateFounded);
    }

    // After we found answer, there is no more need to check the another paths
    if ( duplicateFounded )
    {
        return;
    }

    if ( node.Right != null )
    {
        AddToPath(node.Right, newSum, pathSums, ref duplicateFounded);
    }
}