AlanH AlanH - 3 months ago 11
Javascript Question

Maximum call stack size exceeded. Can't figure out where logic is incorrect

I'm having trouble figuring out how to implement the

contains
method below. I'm trying to use depth first search to find if the tree contains a value, but I'm not sure what's wrong with my implementation.

class Tree {
constructor(val) {
this.value = val;
this.children = [];
}

addChild(val) {
this.children.push(new Tree(val));
}

contains(val) {
if (this.value === val) {
return true;
} else if (this.children.length > 0) {
for (var i = 0; i < this.children.length; i++) {
this.contains(this.children[i].contains(value));
}
// When it gets to the leaf node, how do I go back to the previous call?
// Do I need to return something here?
}

return false; // I may be incorrect on this, but it should return false (execute this line) only when every node has been visited, and there are no more nodes to check.
}
};


So when I do this:

const T = new Tree(100);
T.addChild(50);
T.addChild(40);
T.children[0].addChild(3);

console.log(T.contains(40));


I error out because of a maximum call stack error.

Answer

This line:

this.contains(this.children[i].contains(value));

is questionable because as contains should return a boolean, it doesn't make sense to then check again if the tree contains that boolean value. Also, the problem is on this line: you are calling contains with the exact same arguments (considering this as an argument) within itself, meaning it will never stop, resulting in a "maximum call stack size exceeded" error -- a.k.a. stack overflow.

Instead, you should change it to this:

if (this.children[i].contains(value))
    return true;

That way, the first time it finds the value, it returns. The recursion works as expected because it has a base case, i.e. either finding the value in this.children or falling off the end of the loop.