Search Node In A Tree Using Recursive Javascript Promises

I am stuck in Javascript promise based program and not able to figure out how to get it to return the right value, in a promise format. Given an Tree API that returns children of a

Solution 1:

As the result becomes available asynchronously, the function searchNode will need to return a Promise.

But at two places you do not do this:

1. You should return the first call to tree.getChildren

2. The (recursive) return value of searchNode should be handled as a promise, yet you treat it as a synchronous result:

    childPath = searchNode(searchValue, path+"/"+children[i]);
    if (childPath != null) { // ...etc.

   This is not possible. The return value should be a promise, and so you would need to call the then method on it to get the return value.

As you need to iterate several, maybe all, of the children, you would get as many promises back. But you can and should only return one promise.

Although you could return null in case of not finding the value, it is in my opinion more in line with the idea of promises to produce a rejected promise in that case.

So you could get the result of the first of those promises and then if it resolves, return that promise, but if it rejects (i.e. not found) you should chain the next promise, and the next, ... until one resolves, and return that one. If none of them resolve, or there are no children, a rejected promise should be returned.

Here is the suggested code:

functionsearchNode(searchValue, path){
    return tree.getChildren(path).then(function(children){
        // First look for the value among the immediate childrenfor(let i = 0; i<children.length; i++){
            if(children[i] == searchValue){
                return path;
            }
        }
    // Then look deeperreturn (functionloop(i) {
        if (i >= children.length) {
            returnPromise.reject("not found"); 
        } else { 
            // after asynchronous result comes in, either// continue the loop, or resolve with pathreturnsearchNode(searchValue, path+"/"+children[i])
                .catch(loop.bind(null, i+1));
        }
    })(0);
}

"use strict";
// Simple implementation of treeconst tree = {
    root: {
        '2': {
            '4': {
                '1': {}
            },
            '7': {}
        },
        '0': {}
    },
    getChildren: function(path) {
        returnnewPromise(function (resolve) {
            const node = path.split('/').reduce(function (parent, node) {
                return node === '' || !parent ? parent : parent[node];
            }, tree.root);
            resolve(Object.keys(node));
        });
    }
};

functionsearchNode(searchValue, path){
    return tree.getChildren(path).then(function(children){
        // First look for the value in the immediate childrenfor(let i = 0; i<children.length; i++){
            if(children[i] == searchValue){
                return path;
            }
        }
        // Then look deeperreturn (functionloop(i) {
            if (i >= children.length) {
                returnPromise.reject("not found"); 
            } else { 
                // after asynchronous result comes in, either// continue the loop, or resolve with pathreturnsearchNode(searchValue, path+"/"+children[i])
                    .catch(loop.bind(null, i+1));
            }
        })(0);
    })
}

// DemosearchNode('1', '').then(function (path) {
    console.log(path);
}, function (reason) {
    console.log(reason);
});

A Parallel search alternative

The above solution will not look among the children in parallel. Instead it will wait for the search result for one node before deciding whether the search should be launched for the next sibling node. Depending on how asynchronous the tree.getChildren implementation really is, this may be inefficient:

Imagine a tree where the first child node has a multi-level sub-tree of 1000 nodes, while the value being looked for is an immediate descendant of the second child node. If the search would be launched in parallel, you'd expect the result sooner for such a scenario. On the other hand, the above code will not search other sibling nodes once the value has been found, while with a parallel search the search would continue in the "background" (asynchronously) even after the value has been found and the main promise is resolved. So we should make sure that no deeper searches are initiated when the value has been found.

In order to implement this parallel search idea you would launch searchNode on all children immediately, and apply the then method on each to monitor which one resolves as the first.

For this you could in fact define two generic utility methods -- Promise.not and Promise.some --, much like there already are Promise.race and Promise.all. These functions can be found in other Q&A like "Resolve ES6 Promise with first success?":

// Invert the outcome of a promisePromise.not = promise => promise.then(x => {throw x}, e => e);
// Resolve when the first promise resolvesPromise.some = iterable =>Promise.not(Promise.all(iterable.map(Promise.not)));

Or, you could use a library solution for this, like bluebird's Promise.any.

Then, you would need to add some mechanism to stop initiating deeper searches when the main promise has already been resolved with the found value. For this it suffices to listen to the main promise and flag when it resolves. This can be used to stop the asynchronous code to initiate any further searches.

Here is how you would use that Promise.some function in your case:

functionsearchNode(searchValue, path){
    let resolved = false;

    return (functionsearchNodeSub(path) {
        return tree.getChildren(path).then(function(children){
            // If we already found the value via another parallel search, quitreturn resolved ? true// Otherwise look for the value among the immediate children
                : children.some(child => child == searchValue) ? path
                // If not found there, look deeper -- in parallel
                : Promise.some(children.map(child =>searchNodeSub(path+"/"+child)));
        })
    })(path).then( path => (resolved = true, path) ); // register that we have a result
}

Note the similarity between children.some and Promise.some.

"use strict";
// Simple implementation of treeconst tree = {
    root: {
        '2': {
            '4': {
                '1': {}
            },
            '7': {}
        },
        '0': {}
    },
    getChildren: function(path) {
        returnnewPromise(function (resolve) {
            let node = path.split('/').reduce(function (parent, node) {
                return node === '' || !parent ? parent : parent[node];
            }, tree.root);
            resolve(Object.keys(node));
        });
    }
};

// Invert the outcome of a promisePromise.not = promise => promise.then(x => {throw x}, e => e);
// Resolve when the first promise resolvesPromise.some = iterable =>Promise.not(Promise.all(iterable.map(Promise.not)));

functionsearchNode(searchValue, path){
    let resolved = false;
    
    return (functionsearchNodeSub(path) {
        return tree.getChildren(path).then(function(children){
            // If we already found the value via another parallel search, quitreturn resolved ? true// Otherwise look for the value among the immediate children
                : children.some(child => child == searchValue) ? path
                // If not found there, look deeper -- in parallel
                : Promise.some(children.map(child =>searchNodeSub(path+"/"+child)));
        })
    })(path).then( path => (resolved = true, path) ); // register that we have a result
}

// DemosearchNode('1', '').then(function (path) {
    console.log(path);
}, function (reason) {
    console.log('Not found');
});

Solution 2:

You need to return the .getChildren() promise in searchNode so that you can later wait for it to resolve when returning the childPath:

functionsearchNode(searchValue, path){
  return tree.getChildren(path).then(function(children){ //return the promise so we can later wait for it to resolveif(children.length>0){
        for(var i = 0; i<children.length; i++){
            if(children[i] == searchValue){
                return path;
            } else {
                return searchNode(searchValue, path+"/"+children[i])
                  .then(function(childPath){ //wait for searchNode to completeif (childPath != null) {
                      return childPath;
                    }
                  });
            }
        }
    }
    else{
        returnnull;
    }
  })
}