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+1Example 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);
}
}
}
}