How to get the value of each parent from a nested array of object

Question

So I have a multiple array of object and each object my contain a child.

e.g

const data = [
    {
        id: 1,
        name: 'parent 1',
        children: [
            {
                id: 'c1',
                name: 'child 1',
                children: [
                    {
                        id: 'g1',
                        name: 'grand 1',
                        children: [],
                    },
                ],
            },
        ],
    },
    {
        id: 2,
        name: 'parent 2',
        children: [
            {
                id: 2,
                name: 'c1',
                children: [],
            },
        ],
    },
    { id: 3, name: 'parent 3', children: [] },
];

what I wanted to happen is that if the Id that I'm searching for is 'g1', I would get the result

const result = ['parent 1', 'c1', 'grand 1']

the loop would only stop and get all the names that it went thru until the condition, in this case the id, is met

current approach done

/**
 * Details
 * @param id the value you are searching for
 * @param items nested array of object that has child
 * @param key name of the value you are looking for
 * @returns string of array that matches the id
 * @example ['parent 1', 'c1', 'grand 1']
 */
export function findAll(id: string, items: any, key: string): string[] {
  let i = 0;
  let found;
  let result = [];

  for (; i < items.length; i++) {
    if (items[i].id === id) {
      result.push(items[i][key]);
    } else if (_.isArray(items[i].children)) {
      found = findAll(id, items[i].children, key);
      if (found.length) {
        result = result.concat(found);
      }
    }
  }
  return result;
}

Answer 1

const arr = [
  { id: "1234", parent_id: "", name: "jakson" },
  { id: "4567", parent_id: "1234", name: "obama" },
  { id: "7891", parent_id: "", name: "twinkel" },
  { id: "9876", parent_id: "1234", name: "behara" },
  { id: "1357", parent_id: "7891", name: "aaraku" },
  { id: "6789", parent_id: "7891", name: "mikel" },
  { id: "7892", parent_id: `enter code here`"4567", name: "aaraku" },
  { id: "8765", parent_id: "4567", name: "mikel" },
  { id: "9108", parent_id: "1234", name: "akshra" },
];
const generateChild = (arr) => {
  return arr.reduce((acc, val, ind, array) => {
    const childs = [];
    array.forEach((el) => {
      if (el.parent_id === val.id) {
        childs.push({ id: el.id, name: el.name, parent_id: el.parent_id });
      }
    });
    return acc.concat({ ...val, childs });
  }, []);
};
console.log(generateChild(arr));

output:
(9) [{...}, {...}, {...}, {...}, {...}, ...]
0
:
(4) {id: "1234", parent_id: "", name: "j...}
1
:
(4) {id: "4567", parent_id: "1234", name...}
2
:
(4) {id: "7891", parent_id: "", name: "t...}
3
:
(4) {id: "9876", parent_id: "1234", name...}
4
:
(4) {id: "1357", parent_id: "7891", name...}
5
:
(4) {id: "6789", parent_id: "7891", name...}
6
:
(4) {id: "7892", parent_id: "4567", name...}
7
:
(4) {id: "8765", parent_id: "4567", name...}
8`enter code here`
:
(4) {id: "9108", parent_id: "1234", name...}

Answer 2

const arr = [
  { id: "1234", parent_id: "", name: "jakson" },
  { id: "4567", parent_id: "1234", name: "obama" },
  { id: "7891", parent_id: "", name: "twinkel" },
  { id: "9876", parent_id: "1234", name: "behara" },
  { id: "1357", parent_id: "7891", name: "aaraku" },
  { id: "6789", parent_id: "7891", name: "mikel" },
  { id: "7892", parent_id: "1234", name: "aaraku" },
  { id: "8765", parent_id: "1234", name: "aaraku" },
  { id: "9108", parent_id: "7891", name: "akshra" },
];

let data = [];
let test = [];
for (i = 0; i < arr.length; i++) {
  if (!test.includes(i)) {
    let x = arr[i];
    for (j = i + 1; j < arr.length; j++) {
      if (
        arr[j].name === arr[i].name &&
        arr[j].parent_id === arr[i].parent_id
      ) {
        Object.assign(x, arr[j]);
        test.push(j);
      }
    }
    data.push(x);
  }
}
console.log(data);
var parentChild = [];
for (i = 0; i < data.length; i++) {
  if (data[i].parent_id === "") {
    parentChild.push(data[i]);
  }
}

for (i = 0; i < data.length; i++) {
  for (j = 0; j < parentChild.length; j++) {
    if (data[i].parent_id === parentChild[j].id) {
      if (parentChild[j].child === undefined) {
        Object.assign(parentChild[j], {
          child: [],
        });
        parentChild[j].child.push(data[i]);
      } else {
        parentChild[j].child.push(data[i]);
      }
    }
  }
}
console.log(parentChild);

output:

(8) [{...}, {...}, {...}, {...}, {...}, ...]
0
:
(4) {id: "1234", parent_id: "", name: "j...}
id
:
"1234"
parent_id
:
""
name
:
"jakson"
child
:
(3) [{...}, {...}, {...}]
0
:
(3) {id: "4567", parent_id: "1234", name...}
id
:
"4567"
parent_id
:
"1234"
name
:
"obama"
1
:
(3) {id: "9876", parent_id: "1234", name...}
id
:
"9876"
parent_id
:
"1234"
name
:
"behara"
2
:
(3) {id: "8765", parent_id: "1234", name...}
id
:
"8765"
parent_id
:
"1234"
name
:
"aaraku"
1
:
(3) {id: "4567", parent_id: "1234", name...}
id
:
"4567"
parent_id
:
"1234"
name
:
"obama"
2
:
(4) {id: "7891", parent_id: "", name: "t...}
id
:
"7891"
parent_id
:
""
name
:
"twinkel"
child
:
(3) [{...}, {...}, {...}]
0
:
(3) {id: "1357", parent_id: "7891", name...}
id
:
"1357"
parent_id
:
"7891"
name
:
"aaraku"
1
:
(3) {id: "6789", parent_id: "7891", name...}
id
:
"6789"
parent_id
:
"7891"
name
:
"mikel"
2
:
(3) {id: "9108", parent_id: "7891", name...}
id
:
"9108"
parent_id
:
"7891"
name
:
"akshra"
3
:
(3) {id: "9876", parent_id: "1234", name...}
id
:
"9876"
parent_id
:
"1234"
name
:
"behara"
4
:
(3) {id: "1357", parent_id: "7891", name...}
id
:
"1357"
parent_id
:
"7891"
name
:
"aaraku"
5
:
(3) {id: "6789", parent_id: "7891", name...}
id
:
"6789"
parent_id
:
"7891"
name
:
"mikel"
6
:
(3) {id: "8765", parent_id: "1234", name...}
id
:
"8765"
parent_id
:
"1234"
name
:
"aaraku"
7
:
(3) {id: "9108", parent_id: "7891", name...}
id
:
"9108"
parent_id
:
"7891"
name
:
"akshra"
(2) [{...}, {...}]
0
:
(4) {id: "1234", parent_id: "", name: "j...}
id
:
"1234"
parent_id
:
""
name
:
"jakson"
child
:
(3) [{...}, {...}, {...}]
0
:
(3) {id: "4567", parent_id: "1234", name...}
id
:
"4567"
parent_id
:
"1234"
name
:
"obama"
1
:
(3) {id: "9876", parent_id: "1234", name...}
id
:
"9876"
parent_id
:
"1234"
name
:
"behara"
2
:
(3) {id: "8765", parent_id: "1234", name...}
id
:
"8765"
parent_id
:
"1234"
name
:
"aaraku"
1
:
(4) {id: "7891", parent_id: "", name: "t...}
id
:
"7891"
parent_id
:
""
name
:
"twinkel"
child
:
(3) [{...}, {...}, {...}]

Answer 3

const arr = [
  { id: "1234", parent_id: "", name: "jakson" },
  { id: "4567", parent_id: "1234", name: "obama" },
  { id: "7891", parent_id: "", name: "twinkel" },
  { id: "9876", parent_id: "1234", name: "behara" },
  { id: "1357", parent_id: "7891", name: "aaraku" },
  { id: "6789", parent_id: "7891", name: "mikel" },
  { id: "7892", parent_id: "4567", name: "aaraku" },
  { id: "8765", parent_id: "4567", name: "mikel" },
  { id: "9108", parent_id: "1234", name: "akshra" },
];
const generateChild = (arr) => {
  return arr.reduce((acc, val, ind, array) => {
    const childs = [];
    array.forEach((el) => {
      if (el.parent_id === val.id) {
        childs.push({ id: el.id, name: el.name, parent_id: el.parent_id });
      }
    });
    return acc.concat({ ...val, childs });
  }, []);
};
console.log(generateChild(arr));

output:
(9) [{...}, {...}, {...}, {...}, {...}, ...]
0
:
(4) {id: "1234", parent_id: "", name: "j...}
1
:
(4) {id: "4567", parent_id: "1234", name...}
2
:
(4) {id: "7891", parent_id: "", name: "t...}
3
:
(4) {id: "9876", parent_id: "1234", name...}
4
:
(4) {id: "1357", parent_id: "7891", name...}
5
:
(4) {id: "6789", parent_id: "7891", name...}
6
:
(4) {id: "7892", parent_id: "4567", name...}
7
:
(4) {id: "8765", parent_id: "4567", name...}
8`enter code here`
:
(4) {id: "9108", parent_id: "1234", name...}

Answer 4

Another aproach (not so elegant as above solutions, but it works also)

Very straight forward:
Iterating with for loop down to 3rd level, and when grandchild found in 3rd level, break to escape all 3 levels.

I am curious about how the different solutions would compare performance-wise for a large dataset (let's say a million records).

let i=0, k=0, l=0;

let childrenLength = 0, grandChildrenLength = 0;

let result = [];
let foundGrandChild = false;

function searchGrandChild(searchString) {

  for (i; i< data.length; ++i) {
    if(data.length > 0){
      childrenLength = data[i].children.length;

      if(childrenLength > 0) {
        for (k; k < childrenLength; ++k) {

          if(data[i].children[k] != undefined) {
            grandChildrenLength = data[i].children[k].children.length;

            if(grandChildrenLength > 0) {
              for (l; l < grandChildrenLength; ++l) {
                if(data[i].children[k].children[l] != undefined) {

                  if(data[i].children[k].children[l].id === searchString) {
                    result.push(data[i].name);
                    result.push(data[i].children[k].id);
                    result.push(data[i].children[k].children[l].name);
                    foundGrandChild = true;
                    console.log('Yap, we found your grandchild 😊')
                    console.log(result);
                    break;
                  }
                }
                if(foundGrandChild) break;
              }

            }
          }
          if(foundGrandChild) break;
        }

      }
    }
    if(foundGrandChild) break;
  }

  if(!foundGrandChild) console.log('sorry, we could not find your grandchild 😮')
};

const data = [
    {
        id: 1,
        name: 'parent 1',
        children: [
            {
                id: 'c1',
                name: 'child 1',
                children: [
                    {
                        id: 'g1',
                        name: 'grand 1',
                        children: [],
                    },
                ],
            },
        ],
    },
    {
        id: 2,
        name: 'parent 2',
        children: [
            {
                id: 2,
                name: 'c1',
            },
        ],
    },
    { id: 3, name: 'parent 3', children: [{}] },
];


console.log('Let us search for "g1" ...');
searchGrandChild('g1');

console.log('Let us now search for "g2" ...');
foundGrandChild = false;
searchGrandChild('g2');

Answer 5

You can program a recursive function where you traverse your array at the time you accumulate the objects you traverse in a stack. Once you get an object with the id you want (id == g1) you print the solution. It could be something like this:

'use strict';

function print(stack) {
    //console.log("Printing result...\n");
    let result = "";
    stack.forEach(element => {
        result += element["name"] + " > ";
    });
    console.log(result + "\n");
}

function walkThrough(data, id, stack) {
    if (data !== undefined)
    for (let i = 0; i < data.length; i++) {
        const element = data[i];
        //console.log("Going through " + element["name"] + " with id == " + element["id"]);
        stack.push(element);
        if (element["id"] == id) print(stack);
        else walkThrough(element["children"], id, stack);            
    }
}

const data = [
    {
        "id": 1,
        "name": 'parent 1',
        "children": [
            {
                "id": 'c1',
                "name": 'child 1',
                "children": [
                    {
                        "id": 'g1',
                        "name": 'grand 1',
                        "children": [],
                    },
                ],
            },
        ],
    },
    {
        "id": 2,
        "name": 'parent 2',
        "children": [
            {
                "id": 2,
                "name": 'c1',
            },
        ],
    },
    { "id": 3, "name": 'parent 3', "children": [{}] },
];
//Calling the function to walk through the array...
walkThrough(data, 'g1', []);

Answer 6

I wrote this iterative piece of code that may help you. It basically traverses the structure storing the path from the top-level until the desired id:

function getPath(obj, id) {
    // We need to store path
    // Start stack with root nodes
    let stack = obj.map(item => ({path: [item.name], currObj: item}));
    while (stack.length) {
        const {path, currObj} = stack.pop()
        if (currObj.id === id) {
            return path;
        } else if (currObj.children?.length) {
            stack = stack.concat(currObj.children.map(item => ({path: path.concat(item.name), currObj: item})));
        }
    }
    return null; // if id does not exists
}

This code assumes that your structure is correct and not missing any part (except for children that can be null). Btw, is your answer correct? I guess the path should be: ["parent 1", "child 1", "grand 1"]

Answer 7

The solution below is a recursive function that does the search.

const data = [
    {
        id: 1,
        name: 'parent 1',
        children: [
            {
                id: 'c1',
                name: 'child 1',
                children: [
                    {
                        id: 'g1',
                        name: 'grand 1',
                        children: [],
                    },
                ],
            },
        ],
    },
    {
        id: 2,
        name: 'parent 2',
        children: [
            {
                id: 2,
                name: 'c1',
            },
        ],
    },
    { id: 3, name: 'parent 3', children: [{}] },
];

function getPath(object, search) {
    if (object.id === search) return [object.name];
    else if ((object.children) || Array.isArray(object)) {
        let children = Array.isArray(object) ? object : object.children;
        for (let child of children) {
            let result = getPath(child, search);
            if (result) {
                if (object.id )result.unshift(object.name);
                return result;
            }
        }
    }
}

//const result = ['parent 1', 'c1', 'grand 1']
const result = getPath(data, 'g1');
console.log(result);