Sales Path

[esthicodes]

https://leetcode.com/problems/sum-of-root-to-leaf-binary-numbers/

[esthicodes]

Make sure your peer understands what is required from them in the question. You can check that by asking them to find the minimal Sales Path in the example. If your peer is stuck, ask them to write down all the possible paths in some example tree. After this is done, you may advise them to divide the paths per child of the root node. If your peer is still stuck, ask them to test on an example what happens if you input the function the children of the root node. After that, advise them to look for the connection between the function’s value on the root, and on every child node. Your peer should get full score, only if they manage to find a solution that is O(N) in both runtime and memory space, and only if they do so without any hints on your part. Make sure they know how to explain the correctness of the algorithm, along with the bounds on asymptotic complexity. While the tree in the question is abstract, if your peer needs an implementation you may state that function initially gets a tree node, and that every node has a field holding the cost, and and array holding its children nodes. A good followup question is how to alter the function in order to return all the Sales Paths with minimal cost in an array. Another good question, is how to use the function above to determine the longest or shortest Sales Path path.

[esthicodes]

Pseudocode:

`function getCheapestCost(rootNode):
    n = rootNode.numberOfChildren()

    if (n == 0):
        return rootNode.cost
    else:
        # initialize minCost to the largest integer in the system
        minCost = MAX_INT
        for i from 0 to n-1:
            tempCost = getCheapestCost(rootNode.child[i])
            if (tempCost < minCost):
                minCost = tempCost

return minCost + rootNode.cost`

[esthicodes]

`Obviously iterating through all paths again and again is not a good solution, since its wasteful in terms of time and memory. But intuitively if we find a solution that uses previous calculations somehow. This hints that the solution should involve recursion in some manner.

First we notice that if the root is also a leaf, the best Sales Path, is simply the value in the node itself. This is the base case for the solution. If the root has children, then the minimal Sales Path is also a minimal path from the root’s child. Thus, if we already know the minimal cost for the root’s children, then the minimal cost for the root is simply the minimum of the values for its children plus the value stored in the root itself. A solution to this question, using these facts is given below:`

[esthicodes]

`def get_cheapest_cost(rootNode):
  if not rootNode:
    return 0
  
  def dfs(node, costOfPath):
    if not node:
      return
    
    costOfPath += node.val
    
    # when it is a leaf node, just update the minCost, and return
    if len(node.children) == 0:
      minCost = min(minCost, costOfPath)
      
      return
    
    for child in node.children:
      dfs(child, costOfPath)
      
  minCost = float('inf')
  dfs(rootNode, 0)
  
  return minCost

########################################## 
# Use the helper code below to implement #
# and test your function above           #
##########################################

# A node 
class Node:

  # Constructor to create a new node
  def __init__(self, cost):
    self.cost = cost
    self.children = []
    self.parent = None





'''
Approach 1: Using DFS
  minCost = infinity
  
 totalCostOfPath += node.val
 
 if isLeafNode(node):
  minCost = min(minCost, totalCostOfPath)
  
  
Time Complexity: O(N), N: number of nodes
Space Complexity: O(N), H: height of the tree, height: N, best case: log(N)


Approach 2: 


'''`

[esthicodes]

current cost coming to the root
because of DFS, right now is 0.
root node is 0. cost is 0
sending 0
coming and checking if it is leaf node.

there is a floor, here is 5.
cost is 5.

I am doing a recursion for the 4 of 5, so cost would update it.
Node of DFS is 5 and 5.