Find an object in an array of deeply nested objects recursively

Question

I have an array, and each item is an object with unique Ids. Some items may also have children, and it can have children array inside a children array. I'm trying to pick an item using an Id.

           const array = [
                {
                    uuid: '40E75F3DE56B4B11B3AFBDE46785737B'
                }, {
                    uuid: '9CEF74766BBB4B9682B7817B43CEAE48'
                }, {
                    uuid: '34F209A883D3406FBA6BACD9E07DB1D9',
                    children: [{
                        uuid: 'F429C51BF01C405DA517616E0E16DE4E',
                        children: [{
                            uuid: '8823CFCE7D4645C68991332091C1A05C'
                        }, {
                            uuid: '58A9345E881F48C980498C7FFB68667D'
                        }]
                    }]
                }, {
                    uuid: '152488CC33434A8C9CACBC2E06A7E535'
                }, {
                    uuid: '9152B3DEF40F414BBBC68CACE2F5F6E4'
                }, {
                    uuid: 'B9A39766B17E4406864D785DB6893C3D'
                },
                {
                    uuid: '3J4H4J5HN6K4344D785DBJ345HSSODF',
                    children: [
                        {
                            uuid: 'EAB14DD72DA24BB88B4837C9D5276859'
                        },
                        {
                            uuid: 'FFA80D043380481F8835859A0839512B'
                        },
                        {
                            uuid: '9679687190354FA79EB9D1CA7B4962B1'
                        }
                    ]
                }
            ]

The code below works for a simple array without children. I need a function, or a lodash module that can recursively search the entire array and return the object(item in the array)

findContainingObject(array, uuid) {
    let result = [];
    result = array.filter( item => {
        return item.uuid === uuid
    })
    return result;
}

Expected Outputs:

findContainingObject(array, '40E75F3DE56B4B11B3AFBDE46785737B')

               {
                 uuid: '40E75F3DE56B4B11B3AFBDE46785737B'
               }

findContainingObject(array, '34F209A883D3406FBA6BACD9E07DB1D9')
                {
                    uuid: '34F209A883D3406FBA6BACD9E07DB1D9',
                    children: [{
                        uuid: 'F429C51BF01C405DA517616E0E16DE4E',
                        children: [{
                            uuid: '8823CFCE7D4645C68991332091C1A05C'
                        }, {
                            uuid: '58A9345E881F48C980498C7FFB68667D'
                        }]
                    }]
                }

findContainingObject(array, '58A9345E881F48C980498C7FFB68667D')

                 {
                    uuid: '58A9345E881F48C980498C7FFB68667D'
                 }

skovorodkin · Accepted Answer · 2017-09-05 21:25:58Z

14

This function implements DFS:

function findDFS(objects, id) {
  for (let o of objects || []) {
    if (o.uuid == id) return o
    const o_ = findDFS(o.children, id)
    if (o_) return o_
  }
}

And BFS:

function findBFS(objects, id) {
  const queue = [...objects]
  while (queue.length) {
    const o = queue.shift()
    if (o.uuid == id) return o
    queue.push(...(o.children || []))
  }
}

edited Sep 5, 2017 at 21:25

answered Sep 5, 2017 at 20:46

skovorodkin

10.5k2 gold badges41 silver badges30 bronze badges

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

11 Comments

Brr Switch Over a year ago

Thank you for the solution. I was going along the same line but wouldn't be expensive if I had to look up 'B9A39766B17E4406864D785DB6893C3D'?

Brian Glaz Over a year ago

@VamshiGudipati Yes, it would be expensive. Where is the original array coming from? server side API? Database? Do you have access to it?

Brr Switch Over a year ago

It is the output of a drag-and-drop interface we created and I don't have control over the data coming in. I'm writing a compiler to convert this data into another form of data

skovorodkin Over a year ago

@VamshiGudipati, it's always going to be "expensive" if you don't know in advance an approximate location of an object with given ID. This find function is DFS. If you generally expect your users to search for objects on the first level, then you need to implement BFS.

Brr Switch Over a year ago

Thank you very much for the detailed explanation. I really appreciate it!

|

Thijs · Accepted Answer · 2017-09-05 20:59:09Z

Here is a similar answer, more lines of code for perhaps better readability.

const array = [
  {
      uuid: '40E75F3DE56B4B11B3AFBDE46785737B'
  }, {
      uuid: '9CEF74766BBB4B9682B7817B43CEAE48'
  }, {
      uuid: '34F209A883D3406FBA6BACD9E07DB1D9',
      children: [{
          uuid: 'F429C51BF01C405DA517616E0E16DE4E',
          children: [{
              uuid: '8823CFCE7D4645C68991332091C1A05C'
          }, {
              uuid: '58A9345E881F48C980498C7FFB68667D'
          }]
      }]
  }, {
      uuid: '152488CC33434A8C9CACBC2E06A7E535'
  }, {
      uuid: '9152B3DEF40F414BBBC68CACE2F5F6E4'
  }, {
      uuid: 'B9A39766B17E4406864D785DB6893C3D'
  },
  {
      uuid: '3J4H4J5HN6K4344D785DBJ345HSSODF',
      children: [
          {
              uuid: 'EAB14DD72DA24BB88B4837C9D5276859'
          },
          {
              uuid: 'FFA80D043380481F8835859A0839512B'
          },
          {
              uuid: '9679687190354FA79EB9D1CA7B4962B1'
          }
      ]
  }
  ];
  
  
function findContainingObject(array, itemId) {
  let
    index = 0,
    result = null;
    
  while (index < array.length && !result) {
    const
      item = array[index];
      
    if (item.uuid === itemId) {
      result = item;
    } else if (item.children !== undefined) {
      result = findContainingObject(item.children, itemId);
    }
    
    if (result === null) {
      index++;
    }
  }
  
  return result;
}

console.log(findContainingObject(array, '40E75F3DE56B4B11B3AFBDE46785737B'));
console.log(findContainingObject(array, '34F209A883D3406FBA6BACD9E07DB1D9'));
console.log(findContainingObject(array, '58A9345E881F48C980498C7FFB68667D'));

GibboK · Accepted Answer · 2017-09-05 21:19:22Z

1

Example using recursion.

const data = [{
    uuid: '40E75F3DE56B4B11B3AFBDE46785737B'
  }, {
    uuid: '9CEF74766BBB4B9682B7817B43CEAE48'
  }, {
    uuid: '34F209A883D3406FBA6BACD9E07DB1D9',
    children: [{
      uuid: 'F429C51BF01C405DA517616E0E16DE4E',
      children: [{
        uuid: '8823CFCE7D4645C68991332091C1A05C'
      }, {
        uuid: '58A9345E881F48C980498C7FFB68667D'
      }]
    }]
  }, {
    uuid: '152488CC33434A8C9CACBC2E06A7E535'
  }, {
    uuid: '9152B3DEF40F414BBBC68CACE2F5F6E4'
  }, {
    uuid: 'B9A39766B17E4406864D785DB6893C3D'
  },
  {
    uuid: '3J4H4J5HN6K4344D785DBJ345HSSODF',
    children: [{
        uuid: 'EAB14DD72DA24BB88B4837C9D5276859'
      },
      {
        uuid: 'FFA80D043380481F8835859A0839512B'
      },
      {
        uuid: '9679687190354FA79EB9D1CA7B4962B1'
      }
    ]
  }
];

let find = (data, uuid) => {
  for (let o of data) {
    if (o.uuid === uuid) {
      return o;
    };
    if ('children' in o) {
      let ro = find(o.children, uuid);
      if (ro) {
        return ro;
      }
    }
  }
}

let result = find(data, '9679687190354FA79EB9D1CA7B4962B1')
console.clear();
console.log(result);

answered Sep 5, 2017 at 21:19

GibboK

74.3k149 gold badges453 silver badges676 bronze badges

1 Comment

GibboK Over a year ago

By the way, answer from @skovorodkin is the most complete in my opinion +1 :)

Collectives™ on Stack Overflow

Find an object in an array of deeply nested objects recursively

3 Answers 3

11 Comments

Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

11 Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related