CODEWITHSUNDEEP
javascriptalgorithmrecursion
Marc Fletcher
Marc Fletcher

Reputation: 1072

DFS algorithm continues recursive call, does not return

I am writing DFS in JavaScript, and the algorithm finds the node, but the return statement simple ends the current recursive call, and it continues onward to keep searching the tree. 

dfs(node, target = 0) {
    if (node) {
      if (node.data === target) {
        return node;
      } 
      console.log(node.data);
      this.dfs(node.left, target);
      this.dfs(node.right, target);
    }
  }

Upvotes: 1

Views: 435

Answers (1)

Nina Scholz
Nina Scholz

Reputation: 386570

You need to return in a recursive call the result of the recursice call (which sounds like a tautology). In this case, I assume the result is a node or undefined, which tries first the node itself, then the left part and at last the right part.

dfs(node, target = 0) {
    if (node) {
        if (node.data === target) {
            return node;
        } 
        console.log(node.data);
        return this.dfs(node.left, target) || this.dfs(node.right, target);
    }
}

Upvotes: 2

Related Questions