Home > Mobile >  Deep find object in tree, then return object and the path to it through the tree
Deep find object in tree, then return object and the path to it through the tree

Time:05-15

I've written a recursive function to find a given object and the path within that tree, but when I change the target id (over here : if(tree.targetModuleId === 7)) to 10 I got error:

"message": "Uncaught TypeError: Cannot read properties of undefined (reading 'unshift')"

I supposed to get the path: [1,2,5,6,10].

In the end I need the option that no matter what point to point I want to get a route, I need to get an answer what the route is and if not then get []

I would love to get help on the subject, I enclose a code I made.

let nodes = [
  { sourceModuleId: 1, targetModuleId: 2},
  { sourceModuleId: 1, targetModuleId: 8},
  { sourceModuleId: 2, targetModuleId: 3},
  { sourceModuleId: 2, targetModuleId: 5},
  { sourceModuleId: 8, targetModuleId: 9},
  { sourceModuleId: 3, targetModuleId: 7},
  { sourceModuleId: 5, targetModuleId: 6},
  { sourceModuleId: 6, targetModuleId: 10},

];

function toTree(arr) {
  let arrMap = new Map(arr.map(item => [item.targetModuleId, item]));
  let tree = [];

  for (let i = 0; i < arr.length; i  ) {
    let item = arr[i];

    if (item.sourceModuleId !==1) {
      let parentItem = arrMap.get(item.sourceModuleId);
      
      if (parentItem) {
        let { children } = parentItem;

        if (children) {
          parentItem.children.push(item);
        } else {
          parentItem.children = [item];
        }
      }
    } else {
      tree.push(item);
    }
  }

  return tree;
}

function findInTree(tree) {
  
  if (tree.targetModuleId === 7) {
    let path = [tree.sourceModuleId,tree.targetModuleId];
    return {result: tree, path};
  } 
  if(tree.children){
    for(let i=0; i< tree.children.length;i  ){
      let tmp = findInTree(tree.children);
      if (tmp) {
        tmp.path.unshift(tree.sourceModuleId);
        return tmp;
      }
    }
  }  
  else {
     for (let i = 0;i< tree.length; i  ) {      
      let tmp = findInTree(tree[i]);
      if (tmp) {
        return tmp;
      }
    }
    return [];
  }
}
let tree = toTree(nodes);
let paths = findInTree(tree);
console.log(paths);

CodePudding user response:

Some issues in findInTree:

  • return [] is not correct: this is a truthy value, and so the caller's if (tmp) will be true, and it should not. The data type that your function returns should be consistent. It seems it should be an object with result and path properties, but then it is inconsistent to have a return [] in your code. Make that return null, so to indicate there is no such object and this value will be falsy, given the expected behaviour for the caller. Move this return null out of the else block so it also applies for when the if block does not execute a return.

  • In the if (tree.children) block it is not necessary to loop over those children as that will happen in the recursive call. Note how you never use i in that loop, so it is a waste of time to repeat that body. Just remove the loop.

function findInTree(tree) {
  if (tree.targetModuleId === 7) {
    let path = [tree.sourceModuleId, tree.targetModuleId];
    return {result: tree, path};
  } 
  if (tree.children) { 
      // No need to loop. It will happen in the recursive call
      let tmp = findInTree(tree.children);
      if (tmp) {
        tmp.path.unshift(tree.sourceModuleId);
        return tmp;
      }
  }  
  else {
    for (let i = 0;i< tree.length; i  ) {      
      let tmp = findInTree(tree[i]);
      if (tmp) {
        return tmp;
      }
    }
  }
  return null; // data type consistency
}
  • Related