Can somebody explain to me what the error in my code is? I'm trying to solve this problem as practice, and I keep getting a stack overflow error. I've been looking over it and I just can't seem to find where I'm overflowing the stack in my code. Some things to note:
- I don't actually understand in my code how the children nodes I've created in my test case "know" who their parent node is--because of this, I added those lines assigning their parents to the root node just in case. I understand this probably doesn't look very nice but I just wanted to figure out my main issue!
- I originally initialized the values of parent and children to be null when creating a new SalesNode object, however I was coming across NullReferenceExceptions, so I also changed this part as a safety net.
Problem:
The car manufacturer Honda holds their distribution system in the form of a tree (not necessarily binary). The root is the company itself, and every node in the tree represents a car distributor that receives cars from the parent node and ships them to its children nodes. The leaf nodes are car dealerships that sell cars direct to consumers. In addition, every node holds an integer that is the cost of shipping a car to it.
Take for example the tree below:
0 / | \ 5 3 6 / / \ / \ 4 2 0 1 5 / / 1 10 \ 1A path from Honda’s factory to a car dealership, which is a path from the root to a leaf in the > tree, is called a Sales Path. The cost of a Sales Path is the sum of the costs for every node in the path. For example, in the tree above one Sales Path is 0→3→0→10, and its cost is 13 (0+3+0+10).
Honda wishes to find the minimal Sales Path cost in its distribution tree. Given a node rootNode, write a function getCheapestCost that calculates the minimal Sales Path cost in the tree.
Implement your function in the most efficient manner and analyze its time and space complexities.
For example:
Given the rootNode of the tree in diagram above
Your function would return:
7 since it’s the minimal Sales Path cost (there are actually two Sales Paths in the tree whose cost is 7: 0→6→1 and 0→3→2→1→1)
My code:
using System;
using System.Collections;
class SalesNode
{
public int cost;
public SalesNode[] children;
public SalesNode parent;
public SalesNode()
{
children = new SalesNode[0];
parent = new SalesNode();
}
}
class Solution
{
static void Main(string[] args)
{
SalesNode rootNode = new SalesNode();
rootNode.children = new SalesNode[3];
rootNode.cost = 0;
rootNode.children[0] = new SalesNode {cost = 5};
rootNode.children[1] = new SalesNode {cost = 3};
rootNode.children[2] = new SalesNode {cost = 6};
rootNode.children[0].parent = rootNode;
rootNode.children[1].parent = rootNode;
rootNode.children[2].parent = rootNode;
Console.WriteLine(getCheapestCost(rootNode));
}
public static int getCheapestCost(SalesNode rootNode) {
int minSalesPathCost = Int32.MaxValue;
int currentPathCost = 0;
// Create a stack to implement DFS
Stack salesNodeStack = new Stack();
SalesNode currentNode;
salesNodeStack.Push(rootNode);
while (salesNodeStack.Count > 0) { // Stack is not empty
currentNode = (SalesNode) salesNodeStack.Pop();
currentPathCost += currentNode.cost;
if (currentNode.children.Length == 0) { // Current node is a leaf
minSalesPathCost = Math.Min(minSalesPathCost, currentPathCost);
do { // Keep subtracting costs until back to parent node of next unexplored path
currentPathCost -= currentNode.cost;
currentNode = currentNode.parent;
} while (currentNode != rootNode && currentNode.children.Length == 1);
} else { // Current node has children
foreach (SalesNode child in currentNode.children) {
salesNodeStack.Push(child);
}
}
}
return minSalesPathCost;
}
}
I greatly appreciate any insight. Thanks guys!