Javascript recursive function not returning the result I wanted (tree)

Question

I am trying to do a recursive function to traversal nodes in a tree

• not binary tree, a parent can have more than 2 children. therefore, for loop or forEach is being used here..
• if node has certain property, return true

  traversalNodeTreeWithUrn(root, urn): boolean {
    const nodeList = root;
    for(let i = 0; i < nodeList.length; i++) {
      const site = nodeList[i].childSite;    
      if(site.urn === urn) {
        return true;      
      } 
      else { 
        return this.traversalNodeTreeWithUrn(site,  urn);
      }
    }
    return false;

The problem as recursive, after FOUND return true, it will keep going until all the nodes have been visited and then return final value ( which in my case always return false).

Is there anyway, retain the return true when condition met... or stop the traversal?

Answer 1

for..of with early exit

Seems like you're looking for something like -

function nodeHasUrn(node, urn) {
  // does this node match?
  if (node.urn === urn) return true

  for (const child of node.children ?? [])
    // early exit if a child matches
    if (nodeHasUrn(child, urn)) return true
  return false
}

This works on a tree shape of -

{
  urn: 1,
  children: [
    { urn: 2 },
    { urn: 3 },
    {
      urn: 4,
      children: [
       { urn: 5 },
       { urn: 6 },
       ...
      ]
    }
  ]
}

Here's a functioning demo -

function nodeHasUrn(node, urn) {
  if (node.urn === urn) return true
  for (const child of node.children ?? [])
    if (nodeHasUrn(child, urn)) return true
  return false
}

const tree = {
  urn: 1,
  children: [
    { urn: 2 },
    { urn: 3 },
    {
      urn: 4,
      children: [
       { urn: 5 },
       { urn: 6 },
      ]
    }
  ]
}

console.log(nodeHasUrn(tree, 5)) // true
console.log(nodeHasUrn(tree, 99)) // false

functional style

Recursion is a heritage of functional style and so using it with functional style often yields the best results. Consider writing nodeHasUrn as a pure functional expression -

const nodeHasUrn = ({ urn, children = [] }, match) =>
  urn === match
    ? true
    : children.some(child =>
        nodeHasUrn(child, match)
      )

Which is the same as saying -

const nodeHasUrn = ({ urn, children = [] }, match) =>
  urn === match || children.some(child => nodeHasUrn(child, match))

typescript

type tnode = {
  urn: number,
  children?: Array<tnode>
}

function nodeHasUrn(node: tnode, urn: number): boolean {
  // ...
}

Or use a type generic so urn can number or any other type -

type tnode<T> = {
  urn: T,
  children?: Array<tnode<T>>
}

function nodeHasUrn<T>(node: tnode<T>, urn: T): boolean {
  // ...
}

generators

You named your original method traversalNodeTreeWithUrn, which hints you understand the need to traverse the tree. We can separate the traversal logic into its own function, resulting in a simplified nodeHasUrn, still maintaining the early-exit behavior -

function *traverse(t) {
  yield t
  for (const child of t.children ?? [])
    yield *traverse(child)
}

function nodeHasUrn(t, urn) {
  for (const node of traverse(t))
    if (node.urn == urn)
      return true
  return false
}

const tree = {
  urn: 1,
  children: [
    { urn: 2 },
    { urn: 3 },
    {
      urn: 4,
      children: [
       { urn: 5 },
       { urn: 6 },
      ]
    }
  ]
}

console.log(nodeHasUrn(tree, 5)) // true
console.log(nodeHasUrn(tree, 99)) // false

easter eggs

functional style has a few tricks up its sleeve to blur the lines between it and imperative styles. This approach using callcc is distinguished by the for..of loop not requiring a nested if conditional. Used in this way, callcc is the embodiment of "early exit". If you're interested in this technique, you can learn more about callc introducted in this Q&A -

const callcc = f => {
  const box = Symbol()
  try { return f(unbox => { throw {box, unbox} }) }
  catch (e) { if (e?.box == box) return e.unbox; throw e  }
}

const nodeHasUrn = (node, match) =>
  callcc(exit =>
    (function loop({ urn, children = [] }) {
      if (urn == match) exit(true) // immediate exit
      children.forEach(loop)
      return false
    })(node)
  )

const tree = {
  urn: 1,
  children: [
    { urn: 2 },
    { urn: 3 },
    {
      urn: 4,
      children: [
       { urn: 5 },
       { urn: 6 },
      ]
    }
  ]
}

console.log(nodeHasUrn(tree, 5)) // true
console.log(nodeHasUrn(tree, 99)) // false