Binary Tree Path Sum - two with same value checking

July 28, 2016

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

Write code for binary tree path sum - two with same value checking:


Julia's first writing using C# language: Code is here. 

checklist of code style and design issues:

C# practice is here. 

2.1. if statement is minimum - avoid using if statement.
 Tips: let it fall through base case.
2.2. code style:
   Readable code
   Clean code
2.3. use LINQ to code select clause like SQL statement
2.4. Avoid early return when the duplicate path sum is added. (line 147 - line 154)
2.5. Let main function to take care of discussion of two path sum with same value  (line 123 - 128)
2.6  It is part of the design, one path sum is added to the dictionary twice; so if there are two path sum with same value, the value of dictionary >=4 instead >=2. 

Questions and answers:
1. Which blogs helps you to shape the idea to solve the problem quickly? 
When Julia worked on lowest common ancestor, she used this blog to write a version as well. 

Lowest common ancestor binary tree on geeksforgeek.org, link is here. 

One of Julia's practice documented in the bog is here. 

2. What is most important lessons learned through the practice?

Julia tried to avoid if statement when she designed the solution. Let base case take care of if statement only. Make the code simple as possible, therefore, design of the recursive function is void. line 143 - 162, function pathSumTracking.

Follow up

June 14, 2017
Write C# code to improve a few things. C# practice code is here.

Work on Leetcode 112 - Path sum.