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
– zfrisch, Commented Feb 7, 2018 at 16:06
Possible duplicate of Access / process (nested) objects, arrays or JSON — Heretic Monkey
– Heretic Monkey, Commented Feb 7, 2018 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
– T.J. Crowder, Commented Feb 7, 2018 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
– James Henry, Commented Feb 8, 2018 at 8:55
@T.J.Crowder The IDs are unique, but I did not know about the Map concept :) — James Henry
– James Henry, Commented Feb 8, 2018 at 8:58

T.J. Crowder · Accepted Answer · 2018-02-08 09:42:40Z

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 8, 2018 at 9:42

T.J. Crowder

1.1m201 gold badges2k silver badges2k bronze badges

answered Feb 7, 2018 at 16:12

Jonas Wilms

139k20 gold badges164 silver badges164 bronze badges

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

6 Comments

T.J. Crowder Over a year ago

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...

James Henry Over a year ago

@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

T.J. Crowder Over a year ago

@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 Over a year ago

Jonas - James has replied to my question about IDs: The leaf node IDs are unique, so these solutions work like a charm.

James Henry Over a year ago

@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.

|

T.J. Crowder · Accepted Answer · 2018-02-08 09:46:20Z

1

~~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]));

edited Feb 8, 2018 at 9:46

answered Feb 7, 2018 at 16:14

T.J. Crowder

1.1m201 gold badges2k silver badges2k bronze badges

3 Comments

Jonas Wilms Over a year ago

This is actually a good reduce usecase imo: ids.reduce((node, id) => node.children.find(child => child.id === id), tree)

T.J. Crowder Over a year ago

@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. :-)

James Henry Over a year ago

@T.J.Crowder This is a great example to search with a recursive function multiple IDs. Thx a lot.

Yasir · Accepted Answer · 2018-02-07 16:52:52Z

0

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");

answered Feb 7, 2018 at 16:52

Yasir

6871 gold badge6 silver badges11 bronze badges

Collectives™ on Stack Overflow

Recursive function and Map for accessing Elements in nested Array

3 Answers 3

6 Comments

3 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

6 Comments

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related