Finding a path to target object in nested array of objects in Javascript

Question

I'm currently working through a problem that I'm having some trouble figuring out where I need to find a child node in an array of objects. The target could be one or many levels deep.

The issue is, once I find the object, I also need to push the path I took to get to that object into the resulting data array.

Currently, I have written code that can successfully find the child node:

const buildFullTree = (tree, cat, data = []) => {
  let collection = [tree]

  while (collection.length) {
    let node = collection.shift()

    if (node.id === cat.id) {
      data.push(node)
    }

    collection.unshift(...node.children)
  }

  return data
}

However, this isn't sufficient in terms of getting the path taken to that object.

I'm pretty sure that I need to change this to a recursive depth-first search solution in order to achieve what I'm looking for, but I am not sure how to change the while loop to accomplish this.

Dacre Denny · Accepted Answer · 2018-12-06 20:27:50Z

4

If I understand your question correctly, then perhaps you could revise your path search function like so to achieve what you require:

const buildFullTree = (departmentTree, category, data = []) => {

  const findPath = (node, category) => {

    //If current node matches search node, return tail of path result
    if (node.id === category.id) {
      return [node]

    } else {

      //If current node not search node match, examine children. For first 
      //child that returns an array (path), prepend current node to that 
      //path result
      for (const child of node.children) {
        const childPath = findPath(child, category)
        if (Array.isArray(childPath)) {
          childPath.unshift(child)
          return childPath
        }
      }
    }
  }

  const foundPath = findPath(departmentTree, category)

  // If search from root returns a path, prepend root node to path in
  // data result
  if (Array.isArray(foundPath)) {
    data.push(departmentTree)
    data.push(...foundPath)
  }

  return data
}

const departmentTree = {
  id: 5,
  title: 'department',
  level: 1,
  children: [{
    id: 1,
    parentId: 5,
    title: 'category',
    level: 2,
    children: [{
      id: 15,
      parentId: 1,
      title: 'subcategory',
      level: 3,
      children: []
    }, {
      id: 18,
      parentId: 1,
      level: 3,
      title: 'subcategory',
      children: []
    }, {
      id: 26,
      parentId: 1,
      level: 3,
      title: 'subcategory',
      children: [{
        id: 75,
        parentId: 26,
        level: 4,
        title: 'sub-subcategory',
        children: []
      }, {
        id: 78,
        parentId: 26,
        level: 4,
        title: 'sub-subcategory',
        children: []
      }]
    }]
  }, {
    id: 23823,
    title: 'category',
    level: 2,
    children: []
  }, {
    id: 9,
    parentId: 5,
    level: 2,
    title: 'category',
    children: [{
      id: 48414,
      parentId: 9,
      level: 3,
      title: 'subcategory',
      children: []
    }, {
      id: 2414,
      parentId: 9,
      level: 3,
      title: 'subcategory',
      children: []
    }, {
      id: 42414,
      parentId: 9,
      level: 3,
      title: 'subcategory',
      children: [{
        id: 2323213,
        parentId: 42414,
        level: 4,
        title: 'sub-subcategory',
        children: []
      }, {
        id: 322332,
        parentId: 42414,
        level: 4,
        title: 'sub-subcategory',
        children: []
      }]
    }]
  }]
};

console.log('Path to 2323213:',
  buildFullTree(departmentTree, {
    id: 2323213
  }).map(node => node.id).join(' -> '))

console.log('Path to 23823:',
  buildFullTree(departmentTree, {
    id: 23823
  }).map(node => node.id).join(' -> '))

console.log('Path to -1 (non existing node):',
  buildFullTree(departmentTree, {
    id: -1
  }).map(node => node.id).join(' -> '))

edited Dec 6, 2018 at 20:27

answered Dec 6, 2018 at 19:58

Dacre Denny

30.4k5 gold badges53 silver badges66 bronze badges

Sign up to request clarification or add additional context in comments.

9 Comments

Bill Over a year ago

Yes-that's exactly it! That did it! Thank you very much :D.

Bill Over a year ago

I'm curious if there's a way to refactor findPath to not have to have the category returned in an array, but it's fine the way it is.

Dacre Denny Over a year ago

that would depend on how you need your path represented/returned. It would be possible to return the path as a string of ids in the form: 5 , 9 , 42414 , 2323213 , 2323213 - does that work for you?

Bill Over a year ago

Yeah, that would be fine.

Bill Over a year ago

Also a question. I see we're returning an empty array on a match. Is this to facilitate the logic inside of the for loop? The way I read this, it essentially has builds a path through the children until a match is found. When the match is found, we give back an empty array that childpath can then unshift children into, thus giving us back the desired path. Just wanted to make sure that was the case.

|

Collectives™ on Stack Overflow

Finding a path to target object in nested array of objects in Javascript

1 Answer 1

9 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

9 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related