Find maximum id value in a deeply nested array of objects

user_5227705 0
Viewed 115

I have an tree data structure with each object containing children:

const data = {
  id: 1,
  name: "John",
  parent_id: null,
  children: [{
      id: 2,
      name: "Tess",
      parent_id: 1,
      children: []
    },
    {
      id: 3,
      name: "Tom",
      parent_id: 1,
      children: [{
          id: 4,
          name: "Harry",
          parent_id: 3,
          children: [{
            id: 7,
            name: "Thabo",
            parent_id: 4,
            children: []
          }]
        },
        {
          id: 5,
          name: "Mary",
          parent_id: 3,
          children: []
        },
        {
          id: 6,
          name: "Madge",
          parent_id: 3,
          children: []
        }
      ]
    }
  ]
}

Before I can add a new object to the tree, I need to determine the highest id value currently used, so I can assign the next available number as id for the new user.

To do this I created a new variable with an initial value of 0. Then I iterate over each object in the tree, and if the object's id is higher than the new id, I assign the new id the current id's value (the idea being taking the final value and adding 1 to get the new id).

let newUserID = 0;
const newID = ( root, idKey ) => {
  if ( root.id > idKey ) {
    idKey = root.id;
  }
  root.children.forEach( ( obj ) => {
    newID( obj, idKey );
  });
  return idKey;
}

newUserID = newID( data, newUserID );

console.log( newUserID );

I expected this to return the highest id in the tree as the final value, but what actually happens is that, while the new id does increase until it matches the maximum value, it then starts decreasing again, ending on 1.

This can be seen in this JSFiddle which includes some logging to show the value of the new ID at different points in the function.

I've since solved the issue using a different approach (extracting the id values to a new array, and using Math.max() to find the highest value), but I'd like to understand why my initial approach didn't work as expected. I can see the idKey value is being updated, but then the previous value gets passed back on the recursive call, but I don't know why that's happening or how to prevent it.

recursion arrays javascript
4 Answers

Simply assign the returned value of the recursive call to idKey :

let newUserID = 0;
const newID = ( root, idKey ) => {
  if ( root.id > idKey ) {
    idKey = root.id;
  }
  root.children.forEach( ( obj ) => {
    idKey = newID( obj, idKey ); // <--------
  });
  return idKey;
}

newUserID = newID( data, newUserID );

console.log( newUserID );

Without this assignment, no matter how much you recurse, the value returned will depend only on the result of the if statement at the top. This explains the logs you were getting.

user_24685080

First, as to why your code is broken: You just missed an assignment. Where you have

   newID( obj, idKey );

you are ignoring the resulting value. You need to assign it back to idKey:

    idKey = newID( obj, idKey );

That will solve your problem. We should also note that the variable name newUserID is a bit of a misnomer, since it's not the the new one you will use but the highest one found. Perhaps highestUserID would be less confusing?

However, we should point out that this can be written much more simply, using Math .max to do the heavy lifting and a dollop of recursion. Here's how I might write this:

const maxId = ({id, children = []}) =>
  Math .max (id, ... children .map (maxId))

const data = {id: 1, name: "John", parent_id: null, children: [{id: 2, name: "Tess", parent_id: 1, children: []}, {id: 3, name: "Tom", parent_id: 1, children: [{id: 4, name: "Harry", parent_id: 3, children: [{id: 7, name: "Thabo", parent_id: 4, children: []}]}, {id: 5, name: "Mary", parent_id: 3, children: []}, {id: 6, name: "Madge", parent_id: 3, children: []}]}]}

console .log (maxId (data))

user_12436410

You can use recursion to solve this. Like below

const data = {
  id: 1,
  name: "John",
  parent_id: null,
  children: [
    {
      id: 2,
      name: "Tess",
      parent_id: 1,
      children: [],
    },
    {
      id: 3,
      name: "Tom",
      parent_id: 1,
      children: [
        {
          id: 4,
          name: "Harry",
          parent_id: 3,
          children: [
            {
              id: 7,
              name: "Thabo",
              parent_id: 4,
              children: [],
            },
          ],
        },
        {
          id: 5,
          name: "Mary",
          parent_id: 3,
          children: [],
        },
        {
          id: 6,
          name: "Madge",
          parent_id: 3,
          children: [],
        },
      ],
    },
  ],
};

const findMax = (value) => {
  let max = -Infinity;
  const _findMax = (data) => {
    if (max < data.id) max = data.id;
    data.children.forEach(_findMax);
  };
  _findMax(value);
  return max;
};

console.log(findMax(data));

user_88795270

You can do:

const data = {id: 1,name: 'John',parent_id: null,children: [{ id: 2, name: 'Tess', parent_id: 1, children: [] },{id: 3,name: 'Tom',parent_id: 1,children: [{id: 4,name: 'Harry',parent_id: 3,children: [{ id: 7, name: 'Thabo', parent_id: 4, children: [] }],},{ id: 5, name: 'Mary', parent_id: 3, children: [] },{ id: 6, name: 'Madge', parent_id: 3, children: [] },],},],}
const arr = [...JSON.stringify(data).matchAll(/"id":(\d+)/g)].map(([, n]) => +n)
const result = Math.max(...arr)

console.log(result)

user_19325520
Related