Noah Goodrich
Noah Goodrich

Reputation: 25263

Traverse Tree in Nodejs with Promises

Given a simple user tree:

users:

id | name  | parent_id
1  | Bob   | NULL
2  | Jan   | 1
3  | Mat   | 2
4  | Irene | 2
5  | Ellie | 2
6  | Laura | 5
7  | Uma   | 6

I am trying to walk it with this code:

addChildren: function(db, treeUsers, parentId) {
  const main = this;
  var sql = Sql.select().from('users')
    .where('parent_id = ?', parentId)
    .toParam();

  return db.execute(sql.text, sql.values)
    .then(function([rs,meta]) {
      rs.map(function(obj) { 
          treeUsers[obj.id] = obj;
      });

      return treeUsers;
  });
},

getTreeUsers: function(db, depth) {
  const main = this;
  const rootNodeId = 1;

  var treeUsers = {};
  const getChildren = function(parentId) {
    return main.addChildren(db, treeUsers, parentId).then(function(children) {
      treeUsers = Object.assign(treeUsers, children);
      --depth;
      if(depth < 1) {
        return Promise.resolve(treeUsers);
      }

      return Promise.all(Object.keys(children).map(function(id) { 
          return getChildren(id); 
      }));

  };

  return getChildren(rootNodeId);
});

The desired output would like this:

{
  '2': { id: 2, name: 'Jan'  , parent_id: 2 },
  '3': { id: 3, name: 'Mat'  , parent_id: 2 },
  '4': { id: 4, name: 'Irene', parent_id: 2 },
  '5': { id: 5, name: 'Ellie', parent_id: 2 },
  '6': { id: 6, name: 'Laura', parent_id: 5 },
  '7': { id: 7, name: 'Uma'  , parent_id: 6 }
}

Right now I'm getting an more like this:

[[     {
  '2': { id: 2, name: 'Jan'  , parent_id: 2 },
  '3': { id: 3, name: 'Mat'  , parent_id: 2 },
  '4': { id: 4, name: 'Irene', parent_id: 2 },
  '5': { id: 5, name: 'Ellie', parent_id: 2 },
  '6': { id: 6, name: 'Laura', parent_id: 5 },
  '7': { id: 7, name: 'Uma'  , parent_id: 6 }
} ],
[     {
  '2': { id: 2, name: 'Jan'  , parent_id: 2 },
  '3': { id: 3, name: 'Mat'  , parent_id: 2 },
  '4': { id: 4, name: 'Irene', parent_id: 2 },
  '5': { id: 5, name: 'Ellie', parent_id: 2 },
  '6': { id: 6, name: 'Laura', parent_id: 5 },
  '7': { id: 7, name: 'Uma'  , parent_id: 6 }
} ],
[     {
  '2': { id: 2, name: 'Jan'  , parent_id: 2 },
  '3': { id: 3, name: 'Mat'  , parent_id: 2 },
  '4': { id: 4, name: 'Irene', parent_id: 2 },
  '5': { id: 5, name: 'Ellie', parent_id: 2 },
  '6': { id: 6, name: 'Laura', parent_id: 5 },
  '7': { id: 7, name: 'Uma'  , parent_id: 6 }
} ] ... ]

I'm positive that the problem is the Promise.all(getChildren(..)) call, but I'm not sure how to refactor so that I get back exactly the one final result set.

Upvotes: 0

Views: 242

Answers (2)

trincot
trincot

Reputation: 351403

Some issues:

  • You mutate the treeUsers object in both methods, which means that the object you resolve with, will still be mutated later. Note how you only have one instance of that object for one call of getTreeUsers. Note that the assignment in:

    treeUsers = Object.assign(treeUsers, children);
    

    does not do anything, as Object.assign already mutates the first argument anyway.

  • Promise.all resolves to an array value, where each element contains the treeUsers object. As it was mutated by all separate calls, all these array entries point to the same object reference, explaining the repetitions you see
  • depth is a variable common to each call to getChildren. It would be safer to pass it as argument to be sure that siblings are expanded with the same value for depth

I would just avoid passing the treeUsers object around, as it should really be just the resolved value. Let each promise resolve to the children it can "see" and consolidate the results after each Promise.all promise resolves.

Here is how that could look:

addChildren: function(db, treeUsers, parentId) {
    const main = this,
        sql = Sql.select().from('users')
            .where('parent_id = ?', parentId)
            .toParam();
    return db.execute(sql.text, sql.values).then(function([rs,meta]) {
        // Create a new(!) object and return it
        return Object.assign(...rs.map(function(obj) { 
            return { [obj.id]: obj };
        }));
    });
},

getTreeUsers: function(db, depth) {
    const main = this,
        rootNodeId = 1;

    const getChildren = function(parentId, depth) { // pass depth
        return main.addChildren(db, parentId).then(function(children) {
            if (depth <= 1) {
                return children; // only the children. No need for Promise.resolve
            }
            return Promise.all(Object.keys(children).map(function(id) { 
                return getChildren(id, depth - 1); // pass depth 
            })).then(arr => Object.assign(children, ...arr)); // consolidate 
        });
    }
    return getChildren(rootNodeId, depth);
}

Upvotes: 1

Bergi
Bergi

Reputation: 665584

Yes, Promise.all always returns an array of all the result values. When your calls all return promises that fulfill with the same value, treeUsers, you get an array of those objects. As you always want to make getChildren return always just that object, you can simplify to

function getChildren(parentId) {
  return main.addChildren(db, treeUsers, parentId).then(function(children) {
    Object.assign(treeUsers, children);

    // when `children` is empty, the recursion terminates here
    return Promise.all(Object.keys(children).map(getChildren)).then(() =>
      treeUsers
    );
  });
}

(Of course this does not produce a tree structure)

Upvotes: 0

Related Questions