mocking experience on June 14, 2017 - get cheapst sales path and also find the path information as well.

getCheapstSalePath_WithPath.cs

using System;

class Solution
{
  class Node
  {
    public int cost {get; set;}
    public Node[] children {get; set;}
    public Node parent;

    public Node(int value)
    {
        cost = value; 
    }
  }
   
  static int getCheapestCost(Node rootNode)
  {
    // your code goes here

      string path = string.Empty; 
   
     var cost = getCheapestCostHelper(rootNode, ref path);
     return cost; 
  } 
 
  static int getCheapestCostHelper(Node rootNode, ref string path)
  {
      if(rootNode == null)
      {
        return 0;
      }

      bool noChild = rootNode.children == null || rootNode.children.Length == 0;
      if(noChild)
      {
          path += " " + rootNode.cost.ToString(); 
          return rootNode.cost; 
      }
   
      // assume that there are children
      var value = rootNode.cost;

      int minValue = Int32.MaxValue;
      string minimumPath = string.Empty;
       
      foreach(var child in rootNode.children)
      {
          var backtrackPath = path;
          var current = getCheapestCostHelper(child, ref path);
          if( current < minValue)
          {
              minValue = current;
              minimumPath = path; 
          }

          path = backtrackPath; 
      }

      path = value + " " + minimumPath;
      return value + minValue; 
  }
 
  static void Main(string[] args)
  {
      var root = new Node(0);
      root.children = new Node[2];
      root.children[0] = new Node(3);
      root.children[1] = new Node(6);

      root.children[0].children = new Node[1];
      root.children[0].children[0] = new Node(0);

      root.children[1].children = new Node[2];
      root.children[1].children[0] = new Node(1);
      root.children[1].children[1] = new Node(5);

      getCheapestCost(root); 
  }
}

// depth first search, using recursive calls
// start from root node, then for each child, I will calculate the sum for each child, 
// and then return the minimum 
// do you see any repeated calculations in this approach?
// base case for depth first search - the node does not have child, 
// in other words, left child == right child == null
// I will try to avoid
// write pseduo code first
//  static int getCheapstCost(Node rootNode, IList<string> path)
//  Let me write real code instead, I will change the code structure
//ok

// if(rootNode == null)  return 0
// int min = int.Max;
// var current = rootNode.Value;
// foreach(child in rootNode.Children)
// {
//    var pathSum = getCheapestCost(child); // do you need to add rootnode.value every time? for every child? 
//                                          // its the same thing. you only changed the name
//    min = pathSum < min ? pathSum : min;
// }

// return min + current; // this is better? yea you got it. Let me write C# code, and then test the code quickly. 
// sure if you want to. but you got the solution.
// So let me ask you an extended question. What if i want the actual path and not just the sum.
// I will pass the path in the recursive function
// can you make the change in your pseudo code and show me?