iterating tree in mongoDB

Question

I have a collection of data like this(for example) :

{
    name : "john" ,
    _id : "0"
},
{
    name : "Richard" ,
    parent_id : "0" ,
    _id : "1"
},
{
    name : "Kevin" ,
    parent_id : "0" ,
    _id : "2"
},
{
    name : "William" ,
    parent_id : "1" ,
    _id : "3"
},
{
    name : "George" ,
    parent_id : "3" ,
    _id : "4"
}

I'm trying to write a function to receive an _id and return all children in any depth of this node, for example for _id = 0 I need something like this :

[
    {
        name : "Richard" ,
        parent_id : "0" ,
        depth : "1" ,
        _id : "1"
    },
    {
        name : "Kevin" ,
        parent_id : "0" ,
        depth : "1" ,
        _id : "2"
    },
    {
        name : "William" ,
        parent_id : "1" ,
        depth : "2" ,
        _id : "3"
    },
    {
        name : "George" ,
        parent_id : "3" ,
        depth : "3" ,
        _id : "4"
    }
]

I write several recursive functions to iterate on my mongodb docs but the main problem is I can't handle callbacks (asynchronous) and don't know when and how can I end the recursive function.

How can I do this with mongodb and node.js? Any idea can be useful ,thanks.

Answer 1

There is a 2 famous algorithm that you can use in order to achive your goal
BFS(Breath First search) and DFS(Depth First Search).
For this problem BFS is better than DFS because you can trace your tree in O(logn) You can use DFS too but you have to implement it in recursive way and running time will be O(n) and because your are coding in node js you have to implement it in a asynchronous and it could be a little hard to implement it.
In order to implement BFS algorithm you have to use asynchronous while loop because you have to have mongo query in your while loop and if you use normal javascript your BFS won't work because we are talking about node js not php!!!
So first this is asynchronous while loop that I use in my BFS code

function asyncLoop(iterations, func, callback ,foo) {
        var done = false;
        var loop = {
            next: function() {
                if (done) {
                    return;
                }

                if (iterations) {
                    func(loop);

                } else {
                    done = true;
                    if(callback) callback(foo);
                }
            },

            isEnd : function(){
                return done ;
            } ,

            refresh : function(it){
                iterations = it ;
            },

            break: function() {
                done = true;
                callback();
            }
        };
        loop.next();
        return loop;
    }

And this is BFS algorithm node js code:

function bfs (_id ,callback){
    _id = String(_id);
    var q = [] ,res = [] ;

    db.tasks.findOne({ _id : _id }).lean().exec(function(err,root){
        root.depth = 0 ;
        q.push(root);

        asyncLoop(q.length ,function(loop){
            res.push(q[0]);
            db.tasks.find({ _parent : q[0]._id }).lean().exec(function(err,new_nodes){
                if(err) console.log(err);
                else {
                    var d = q[0].depth ;
                    q.shift();
                    loop.refresh(new_nodes.length + q.length);
                    if(new_nodes.length > 0){
                        new_nodes.forEach(function(new_node){
                            new_node.depth = d+1 ;
                            q.push(new_node);
                        });
                    }
                    loop.next();
                }
            });

        },function(){ callback(res) });
    });
}

Note:I also save depth of each query so you can have depth of each query and know where this query is in tree.