Iterative Deepening Depth-first Search (DFS) Javascript

iddfs.js

// Iterative deepening DFS

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

// takes in a tree and truncates to a max depth
const truncatedDFS = (node, id, maxDepth, currentDepth = 1) => {
  if (node.id === id) return true
  for (let i = 0; i < node.children.length; i++) {
    let found
    // check to make sure current depth is not greater than max depth
    if (currentDepth < maxDepth) {
      found = truncatedDFS(node.children[i], id, maxDepth, currentDepth + 1)
    }
    if (found) return true
  }
  return false
}

/**
  * Check if the tree has a given node using iterative deepening DFS
  * @param {Node} root - the starting point (root) node
  * @param {string} id - the identifier of the node that we're looking for
  * 
  * @returns {boolean} - true if found, false if not
  */
const hasNode = (node, id) => {
  // run truncated DFS iteratively until we run out of depths
  // NOTE currently bounded to a max depth of 100
  let maxDepth = 100
  let depth = 1
  let found
  
  // as long as we haven't exhaused our depth and haven't found anything yet, keep running
  while (depth < maxDepth && !found) {
    found = truncatedDFS(node, id, depth)
    depth = depth + 1
  }
  
  // if we found something, return true
  if (found) return true
  
  // otherwise, return false
  return false
}

console.log(hasNode(tree, "7")) // => true
console.log(hasNode(tree, "5")) // => true
console.log(hasNode(tree, "100")) // => false