Binary tree root to leaf path minimum path value with the path

Nov. 15, 2017

I like to document my mock interview practice on this algorithm. The topic is about analysis of the algorithm, how to reason to find possible bugs?

Here is C# practice code.  I added line 27 to line 32 to fix the bug since the peer told me that the edge case with no children. The advice from the peer is "After writing the code need to analyze more before running it". 

Story of analysis

I need to explain how the depth first search works since peer asked if I should add an argument of function to pass the existing value. I did explain the algorithm in the mock interview, but the peer felt that he did not know C# very well and got confused. 

I like to write my story to show how I analyze the algorithm after the mock interview, try to make the explanation to a very good one. 

Let us go over  a tree with the following nodes:

      0
  /   |   \
 4   3   6
 /
3

The depth first search algorithm can be solved this way. The root node with value 0 has a tree, to find its minimum path to the leaf node, first if the root node is null, then value is 0; if the root node is not null, and if the root node has no children, it is a base case, the minimum path is the value of root. Otherwise, go over each children of root node with value 0, and go to each child in the array [node 4, node 3, node 6], and ask each node to get its minimum value for the path, denoted as Mi, and just add root node value 0 to Math.Min(Mi, i from 0 to 2).

Miss a base case

From the above paragraph, I highlighted the base case I missed in mock interview using brown color, and the peer had to tell me that there will be a problem if there is no children. In other words, in the tree showing in the above diagram, if the root node with value 0 has no children, it is a base case, the minimum path is the value of root.