Searching a dynamically generated, multilevel array of objects

Question

I currently have a Javascript array of objects like so:

myArray = [
    {
        id: 'top-id1',
        title: 'title1',
        subElements: [
            {
                id: 'id2',
                title: 'title2',
                subElements: [
                    {
                        id: 'id3',
                        title: 'title2',
                        subElements: [
                            ...
                        ]
                    }
                ]
            },
            {
                id: 'id4',
                title: 'title4',
             },
             ...
         ]
     },
     {
         id: 'top-id5',
         title: 'title5',
         subElements: [
             ...
         ]
     },
     ...
];

This array can technically be infinitely long and infinitely deep (through the subElements), but in practice it will only have 4 max objects at the top level and go 4 levels deep max so performance and runtime isn't a huge concern.

What I'm trying to find: Given any id, I need to return the id of the top level object that contains the first id. So if I'm given 'id3', I need to return 'top-id1'. And if I'm given 'top-id5', I also need to return 'top-id5'. For what it matters, this is in the context of a React application. Can someone help me figure out an algorithm to do so?

A DFS/BFS "tree traversal" type search algorithm would be what you are looking for, depending on which result you wanted to return. You probably want the DFS (depth first search) one. — Drew Reese, Jun 25 '19 at 15:41
This is not exactly a duplicate, but the answers to https://stackoverflow.com/q/56066101 can probably help you with this. — Scott Sauyet, Jun 25 '19 at 16:11

score 2 · Accepted Answer · edited Jun 26 '19 at 06:51

This will work for your case.

const myArray = [{ id: 'top-id1', title: 'title1', subElements: [{ id: 'id2', title: 'title2', subElements: [{ id: 'id3', title: 'title2', subElements: [ ] }] }, { id: 'id4', title: 'title4', }, ] }, { id: 'top-id5', title: 'title5', subElements: [ ] }, ];

function searchTree(element, matchingId) {
  if (element.id == matchingId) {
    return element;
  } else if (element.subElements != null) {
    var i;
    var result = null;
    for (i = 0; result == null && i < element.subElements.length; i++) {
      result = searchTree(element.subElements[i], matchingId);
    }
    return result;
  }
  return null;
}

function searchTopNode(element, data) {
  for (var i = 0; i < data.length; i++) {
    if (searchTree(data[i], element) != null)
      return data[i].id;
  }
}

console.log(searchTopNode('id3', myArray));
console.log(searchTopNode('top-id5', myArray));

score 0 · Answer 2 · edited Jun 26 '19 at 06:52

const myArray = [{ id: 'top-id1', title: 'title1', subElements: [{ id: 'id2', title: 'title2', subElements: [{ id: 'id3', title: 'title2', subElements: [ ] }] }, { id: 'id4', title: 'title4', }, ] }, { id: 'top-id5', title: 'title5', subElements: [ ] }, ];

function deepSearch(obj, result) {

  if (typeof obj !== 'object') {
    return;
  }
  if (Array.isArray(obj)) {
    for (let i = 0, elem; elem = obj[i]; i++) {
      deepSearch(elem, result);
    }
    return;
  }
  if (!!obj['id']) {
    result.push(obj.id);
  }
  if (!!obj['subElements'] && Array.isArray(obj.subElements)) {
    deepSearch(obj.subElements, result);
  }
}

const results = [];
deepSearch(myArray, results);
console.log(results);

Explanation and a snippet is preferred. I made you a snippet. How to get the top-id from id3? — mplungjan, Jun 26 '19 at 06:53

score 0 · Answer 3 · edited Jun 26 '19 at 11:27

const myArray = [{ id: 'top-id1', title: 'title1', subElements: [{ id: 'id2', title: 'title2', subElements: [{ id: 'id3', title: 'title2', subElements: [ ] }] }, { id: 'id4', title: 'title4', }, ] }, { id: 'top-id5', title: 'title5', subElements: [ ] }, ];


function findRoot(array, id) {
  let node = null
  array.forEach(x => {
    if (x.id == id) {
      node = x
    } else {
      if (x.subElements) {
        let found = findRoot(x.subElements, id)
        if (found)
          node = x
      }
    }
    if (node)
      return
  })
  return node
}

var result = findRoot(myArray, 'id3')
if (result && result.id)
  document.querySelector('#result').innerHTML = result.id

<div id="result"></div>

Maybe something like this?

If you click `[<>]` you can make a [mcve] to show it works. Here is the array: `const myArray = [{ id: 'top-id1', title: 'title1', subElements: [{ id: 'id2', title: 'title2', subElements: [{ id: 'id3', title: 'title2', subElements: [ ] }] }, { id: 'id4', title: 'title4', }, ] }, { id: 'top-id5', title: 'title5', subElements: [ ] }, ]; ` — mplungjan, Jun 26 '19 at 06:54

Searching a dynamically generated, multilevel array of objects

3 Answers3