CODEWITHSUNDEEP
javascriptalgorithmrecursiondata-structures
Dustin Wyatt
Dustin Wyatt

Reputation: 4244

Finding parent objects in nested arrays of objects. How?

I have a data structure that looks like this:

var someDataStructure = [
  {
    opts: {_id:1}
  },
  {
    opts: {_id: 2},
    children: [
      {
        opts: {_id: 3},
        children: [
          {
            opts: {_id: 4}
          }
        ]
      }
    ]
  },
  {
    opts: {_id: 5}
  },
  {
    opts: {_id: 6},
    children: [
      {
        opts: {_id: 7},
        children: [
          {
            opts: {_id: 8}
          }
        ]
      }
    ]
  }  
];

That's an array of objects, all with an opts property, and an optional children property. If it exists the children property will be an array of the same sort of objects.

Given any opts._id, I need to find the _id of all parent objects. The _id's I give here are only sequential for convenience. You may not assume they are sequential integers

This project is using both jquery and lodash so both of those libraries are available for use.

Example desired output:

I have no problem recursing in and finding the given _id. However, I'm feeling dumb and stuck on maintaining the array of parents.

Upvotes: 1

Views: 2583

Answers (2)

Linus
Linus

Reputation: 3580

A solution returning found status and parents if found.

function getParentsHelper(tree, id, parents) {
    if (tree.opts._id == id) {
        return {
            found: true,
            parents: parents
        };
    }
    var result = {
        found: false,
    }
    if (tree.children) {
        $.each(tree.children, function(index, subtree) {
            var maybeParents = $.merge([], parents);
            if (tree.opts._id != undefined) {
                maybeParents.push(tree.opts._id);
            }
            var maybeResult = getParentsHelper(subtree, id, maybeParents);
            if (maybeResult.found) {
                result = maybeResult;
                return false;
            }
        });
    }
    return result;
}

function getParents(data, id) {
    var tree = {
        opts: { },
        children: data
    }
    return getParentsHelper(tree, id, []);
}

Usage example:

console.log(getParents(someDataStructure, 4).parents);
console.log(getParents(someDataStructure, 3).parents);
console.log(getParents(someDataStructure, 8).parents);
console.log(getParents(someDataStructure, 7).parents);

Upvotes: 3

Alessandro Marchisio
Alessandro Marchisio

Reputation: 545

for one children this works:

function writeParent(id, arr) {

    var ct = 0;
    var found = false;
    var parentsLine = []; 

    arr.some(function (e){
        parentsLine = []

        for (var curr = e; curr.children != null; curr = curr.children[0]) {
            if (id == curr.opts._id) {
                found = true;
                return true;
            } 
            parentsLine.push(curr.opts._id)    

        }  

        if (id == curr.opts._id) {
            found = true;
            return true;
        } 


    })
    if (found) {
        return parentsLine;
    } else {
        return "ERR: elm not found";
    }    
}

see http://jsfiddle.net/alemarch/ufrLpLfx/11/

Upvotes: 0

Related Questions