Recursive function and Map for accessing Elements in nested Array

Question

Situation

I have an nested Array and I have a ID to search for. Like "A_02_02_01_03"
Every Element in an array has a element called "children", that is a array
My method gets pretty long when I'm searching in the 4th Layer.

Example Array

var tree= [
  {
    "name": "i2",
    "children": [
      {
        "name": "d1",
        "children": [],
        "id": "DW_02_01",
        "beschreibung": "",
        "table": []
      },
      {
        "name": "d2",
        "children": [
          {
            "name": "e1",
            "children": [
              {
                "name": "a1",
                "children": [],
                "id": "A_02_02_01_01",
                "beschreibung": "",
                "table": []
              },
              {
                "name": "a2",
                "children": [],
                "id": "A_02_02_01_02",
                "beschreibung": "",
                "table": []
              },
              {
                "name": "a3",
                "children": [],
                "id": "A_02_02_01_03",
                "beschreibung": "",
                "table": []
              }`enter code here`
            ],
            "id": "E_02_02_01",
            "beschreibung": "",
            "table": []
          },
          {
            "name": "e2",
            "children": [],
            "id": "E_02_02_02",
            "beschreibung": "",
            "table": []
          }
        ],
        "id": "DW_02_02",
        "beschreibung": "",
        "table": []
      },
      {
        "name": "d3",
        "children": [],
        "id": "DW_02_03",
        "beschreibung": "",
        "table": []
      }
    ],
    "id": "IW_02",
    "beschreibung": "",
    "table": []
  },
  {
    "name": "i3",
    "children": [],
    "id": "IW_03",
    "beschreibung": "",
    "table": []
  }
]

Constructing IDs

var daIW = "IW_02";
var daDW = "DW_02_02;
var daE = "E_02_02_01;
var daA = "A_02_02_01_03";

Getting all my indices

var iw_index = tree.findIndex(element => element.id == daIW);
var dw_index = tree[iw_index]["children"].findIndex(element => element.id == daDW);
var e_index = tree[iw_index]["children"][dw_index]["children"].findIndex(element => element.id == daE);
var a_index = tree[iw_index]["children"][dw_index]["children"][e_index]["children"].findIndex(element => element.id == daA);

Accessing my Element

var elementName = tree[iw_index]["children"][dw_index]["children"][e_index]["children"][a_index].name;

Question

Is there a shorter way for accessing the deepest Element "A_02_02_01_03" then searching for every index?

What is the result you're looking for? You just want to return the child that contains whatever id? — zfrisch, Feb 07 '18 at 16:06
Possible duplicate of [Access / process (nested) objects, arrays or JSON](https://stackoverflow.com/questions/11922383/access-process-nested-objects-arrays-or-json) — Heretic Monkey, Feb 07 '18 at 16:15
Are the `id` values on the leaf nodes (A_02_02_01_03 and such) unique? If so, any particular reason you can't just create a map of them? — T.J. Crowder, Feb 07 '18 at 16:16
@zfrisch In the End I want to change, move or delete this Element. First I wanted to get there. I was just exhausted for always writing something like this: `tree[iw_index]["children"][dw_index]["children"][e_index]["children"].splice(new_index, 0, tree[iw_index]["children"][dw_index]["children"][e_index]["children"].splice(old_index, 1)[0]);` — James Henry, Feb 08 '18 at 08:55
@T.J.Crowder The IDs are unique, but I did not know about the Map concept :) — James Henry, Feb 08 '18 at 08:58

score 2 · Accepted Answer · edited Feb 08 '18 at 09:42

2

You may want recursion to search the tree deep first:

function search(array = [], id){
  for(const node of array){
    if(node.id === id) return node;

    const sub = search(node.children, id);
    if(sub) return sub;
  }
}

So you can do:

const result = search(tree, "A_02_02_01_03");

If you want to find multiple items, it might be better to build up a hashtable that stores all id/node pairs, so lookup is very fast then:

function createLookup(array, hash = new Map){
  for(const node of array){
    hash.set(node.id, node);
    createLookup(node.children, hash);
  }
  return hash;
}

So you can do:

const hash = createLookup(tree);
const result = hash.get("A_02_02_01_03");

edited Feb 08 '18 at 09:42

T.J. Crowder

1,031,962
187
1,923
1,875

answered Feb 07 '18 at 16:12

Jonas Wilms

132,000
20
149
151

1

This assumes the IDs of those leaf nodes are unique. From the fact the OP is using other IDs to get there, I'm not sure I'd make that assumption... – T.J. Crowder Feb 07 '18 at 16:15
1

@Jonas W. Big thx for your example. Recursion was the needed concept for my brain to solve this. I also tried your hashtable example. This throws me an error: `InternalError: too much recursion` – James Henry Feb 08 '18 at 09:01
1

@JamesHenry: That's just a typo in the code (`createLookup(array, hash);` should have been `createLookup(node.children, hash);`), I've fixed it. – T.J. Crowder Feb 08 '18 at 09:42
1

Jonas - James [has replied](https://stackoverflow.com/questions/48668232/other-method-for-accessing-element-in-nested-array-then-indexof?noredirect=1#comment84359661_48668232) to my question about IDs: The leaf node IDs *are* unique, so these solutions work like a charm. – T.J. Crowder Feb 08 '18 at 09:43
2

@T.J.Crowder Thx guys for your time, I learned a lot. I tried both solutions. They work really good and made my code so much clearer and shorter. – James Henry Feb 08 '18 at 11:03
@james glad to help :) – Jonas Wilms Feb 08 '18 at 14:53

T.J. Crowder · Answer 2 · 2018-02-08T09:46:20.363

~~I'm assuming that for some reason you can't just search for the entry with id == "A_02_02_01_03". E.g., that you need the other IDs for some reason.~~

Now that you've confirmed that the leaf node IDs are unique, Jonas w's answer which only uses the leaf node ID (e.g., "A_02_02_01_03") will work. If you have those other IDs available, that can make the process faster by avoiding visiting nodes you don't need to visit, but you'd have to have a very big tree for that to matter.

If it does matter, this answer still applies:

I'd probably use a recursive function:

function find(node, ids, index = 0) {
    const id = ids[index];
    const entry = node.find(e => e.id == id);
    if (!entry) {
        return null;
    }
    ++index;
    return index < ids.length ? find(entry.children, ids, index) : entry;
}

and then call it like this:

const result = find(tree, [daIW, daDW, daE, daA]);

That assumes you want the entry as the result.

Live Example:

var tree= [
  {
    "name": "i2",
    "children": [
      {
        "name": "d1",
        "children": [],
        "id": "DW_02_01",
        "beschreibung": "",
        "table": []
      },
      {
        "name": "d2",
        "children": [
          {
            "name": "e1",
            "children": [
              {
                "name": "a1",
                "children": [],
                "id": "A_02_02_01_01",
                "beschreibung": "",
                "table": []
              },
              {
                "name": "a2",
                "children": [],
                "id": "A_02_02_01_02",
                "beschreibung": "",
                "table": []
              },
              {
                "name": "a3",
                "children": [],
                "id": "A_02_02_01_03",
                "beschreibung": "",
                "table": []
              }
            ],
            "id": "E_02_02_01",
            "beschreibung": "",
            "table": []
          },
          {
            "name": "e2",
            "children": [],
            "id": "E_02_02_02",
            "beschreibung": "",
            "table": []
          }
        ],
        "id": "DW_02_02",
        "beschreibung": "",
        "table": []
      },
      {
        "name": "d3",
        "children": [],
        "id": "DW_02_03",
        "beschreibung": "",
        "table": []
      }
    ],
    "id": "IW_02",
    "beschreibung": "",
    "table": []
  },
  {
    "name": "i3",
    "children": [],
    "id": "IW_03",
    "beschreibung": "",
    "table": []
  }
];

var daIW = "IW_02";
var daDW = "DW_02_02";
var daE = "E_02_02_01";
var daA = "A_02_02_01_03";

function find(node, ids, index = 0) {
    const id = ids[index];
    const entry = node.find(e => e.id == id);
    if (!entry) {
        return null;
    }
    ++index;
    return index < ids.length ? find(entry.children, ids, index) : entry;
}

console.log(find(tree, [daIW, daDW, daE, daA]));

This is actually a good reduce usecase imo: `ids.reduce((node, id) => node.children.find(child => child.id === id), tree)` — Jonas Wilms, Feb 07 '18 at 16:19
@JonasW.: If we were using the same ID for each level. I imagine we could shoe-horn it into a `reduce` even if using different IDs for different levels, but it's clearer if we don't. :-) — T.J. Crowder, Feb 07 '18 at 16:24
@T.J.Crowder This is a great example to search with a recursive function multiple IDs. Thx a lot. — James Henry, Feb 08 '18 at 09:02

score 0 · Answer 3 · answered Feb 07 '18 at 16:52

Try the following recursive function

//Function

  function getelement(vtree, id) {
      vtree.forEach(function(treeitem) {
        if(treeitem["id"] === id) {
            console.log(treeitem);
        }
        else if(treeitem["children"].length){
            getelement(treeitem["children"], id);
        }
    });
  };

//Caller

getelement(tree,"A_02_02_01_03");

Recursive function and Map for accessing Elements in nested Array

3 Answers3