Home > Net >  Recursive DFS String search returning undefined in typescript
Recursive DFS String search returning undefined in typescript

Time:05-08

I am working on a DFS based search algorithm for a string like this

function alias_id_lookup(node, visitedNodeIds, target_id): string{
  visitedNodeIds.push(node.id)
  if (node.id == target_id){
    return node.name as string
  }
  
  for (var childNode of node.children) {
    if(!visitedNodeIds.includes(childNode.id)){
      alias_id_lookup(childNode, visitedNodeIds, target_id)
    }
  }
}

From some debugging via print statments I know that the correct node is being found, however the funtion itself is returning undefined.

I figure my recursion is broken however I cannot spot exactly what I have messed up.

Any help is appriciated, thanks.

CodePudding user response:

You need to return the result of the function call that found the node.

function alias_id_lookup(node, visitedNodeIds, target_id): string{
  visitedNodeIds.push(node.id)
  if (node.id == target_id) {
    return node.name as string
  }
  
  for (var childNode of node.children) {
    if (!visitedNodeIds.includes(childNode.id)) {
      var res = alias_id_lookup(childNode, visitedNodeIds, target_id)
      if (res !== undefined) return res;
    }
  }
}
  • Related