Recursive function to find top level parent given an id

Question

Given the following data set:

const accounts = [
  {id: 2, children: [1,22,69], parentId: null},
  {id: 3, children: [140, 122, 580], parentId: null},
  {id: 1, children: [4,5,6], parentId: 2},
  {id: 22, children: [8,9,2], parentId: 2},
  {id: 4, children: [45,54,61], parentId: 1},
  {id: 6, children: [40,89,20], parentId: 1},
  {id: 40, children: [], parentId: 6},
  ....
]

I need to create a function that takes and id as argument and returns a tree, starting with the top most level parent and it's children (and siblings).

In the above example, there are only 2 top level "accounts", id:2 and id:3. So the function call might look like findTree(89) , it should return the tree starting with the account id 2, and it's children, but will obviously leave out account id 3 and it's children, since that top level account has nothing to do with top level account of id 2, so the ideal response would be:

{
 id: 2,
 children: [
   { id: 1, children: [{id: 540, children: [{ id: 78},{}], parentId:1], parentId: 2},
   .....
 ],
 parentId: null
}

What would be the best way to go about it ? I've tried a recursive function but I'm not getting anywhere near to a solution.

EDIT: Here part of the code: (groupArray is an array containing all items in a flat list, without hierarchy)

const makeTreeById = itemId => {
 const startNode = _.find(groupArray, {id: itemId}) // grab the actual item, not the id
 findTopParent(startNode)
}

and then the findTopParent fn

const findTop = item => {
 let top = item;
 if(top.parentId) {
  top = _.find(groupArray, {id: top.parentId}
  return findTop(top)
 }
 return top;
}

I was creating that function to simply have it return the top level account and from there I was planning on constructing the actual tree, the problem is that top does get me the top level but at some point it get reassigned with the immediate parent.

SECOND EDIT: Sorry about all the confusion guys, as you can see, I'm really new. I have an array that includes all items I would need. So it kinda looks like this:

// children here are only ids, not the actual elements, the element are part of // the list, but the children array for each element is just a reference.
data = [
 {id: 1, children: [4,5,6], parentId: null}, 
 {id: 2, children: [7,8,9], parentId: null},
 {id: 3, children: [10,11,12], parentId: null},
 {id: 4, children: [13,14,15], parentId: 1},
 {id: 10, children: [20,21,22], parentId: 3}
 {id: 14, children: [], parentId: 4}
 ....
]

Answer 1

actually they are many way to achieve the expected tree. In performance manner you should determine if you will have complexity (in term of iteration) on the deep of your tree or | and on how many items in total you will have.

I have assume the complexity will be more on how many items in total you will have.

exemple : big amount of accounts with only small amount of nested childrens.

---

Introduction : Following you have type and sample array.

interface IEntity {
  id: number;
  children: number[];
  parentId?: number;
}

interface IEntityNested {
  id: number;
  children: IEntityNested[];
  parentId?: number;
}

const accounts: IEntity[] = [
  {id: 1, children: [3], parentId: null},
  {id: 2, children: [], parentId: null},
  {id: 3, children: [4], parentId: 1},
  {id: 4, children: [], parentId: 3},
];

For that i prupose you to start by searching for any particular id what is the top of you tree. The element which doesn't have any other top element.

const findTopParent = (id: number): IEntity => {

  let account = accounts.find(acc => acc.id === id);
  if(account.parentId !== null) {
    account = findTopParent(account.parentId);
  }
  return account;
};

For id 4 it should return account id 1

const topParent = findTopParent(4);
console.log(topParent.id); // Print 1.

then from your topParent you can build the nested tree from the top to the bottom.

const buildTreeFromSpecificAccount = (account: IEntity): IEntityNested => {
  const nestedAccount = {...account,children: []};

  account.children.forEach(childId => {
    nestedAccount.children.push(
      buildTreeFromSpecificAccount(
        accounts.find(acc => acc.id === childId)
      )
    );
  })
  return nestedAccount;
}
// Build the tree from the top parent.
const tree = buildTreeFromSpecificAccount(topParent);

And voilà !

---

Side note :

You can way more improve the performance by changing your data array by indexed object like following :

const accountOrdered: {[id: number]: IEntity} = {
  1: {id: 1, children: [3], parentId: null},
  2: {id: 2, children: [], parentId: null},
  3: {id: 3, children: [4], parentId: 1},
  4: {id: 4, children: [], parentId: 3},
};

Like this instead of doing accounts.find(acc => acc.id === childId) looping on your array to find entry by id. you can do accountOrdered[childId]

---

live sample

Answer 2

You can find the desired results with function topParent. Just look for parent being null in each iteration.

const accounts = [
  {id: 2, children: [1,22,69], parentId: null},
  {id: 3, children: [140, 122, 580], parentId: null},
  {id: 1, children: [4,5,6], parentId: 2},
  {id: 22, children: [8,9,2], parentId: 2},
  {id: 4, children: [45,54,61], parentId: 1},
  {id: 6, children: [40,89,20], parentId: 1},
  {id: 40, children: [], parentId: 6}
];

function topParent(id) {
  var obj = accounts.find((v) => v.id == id);
  return obj.parentId == null ? obj : topParent(obj.parentId)
}

console.log(topParent(6));