6

I have a javascript function that walks a tree recursively. It has two "flag" variables that are set to false or true above the scope of the function itself, and so if a flag is set to true one time while the "walkTree" function is being recursed, it will be true for every recursion. On the other hand, the for loop might exist the function with a return as well if something is for. The problem I have is when there are too many recursions I get an error.

I'd like to prevent this problem by making this recursive function asynchronous, I've tried putting the sub walkTree() call inside the for loop into a setTimeout, but the problem I have now is that the rest of the function will be executed (and might return the wrong value) before the rest of the asynchronous stuff is done. So how can I make this asynchronous while still making sure the right value will be returned (and not the top function call in the recursion)?

As you can see the end of the function makes use of that flagB "variable" shared by all calls, and so we need to make sure all the recursive calls have been completed (and returned something) before the top one checks for these conditionals. Thanks!

var flagA = false;
var flagB = false;

var walkTree = function (n) {
  var sub;

  for (var i = 0; i < n.children.length; i++) {
      sub = walkTree(n.children[i]);
      if (sub === 'something-special') {
        return sub;
      }
  }

  var test = doSomethingWith(n);

  if (test === "something") {
    flagA = true;
  }

  if (test === "something-else") { 
    flagB = true;
  }

  if (flagB === true) {
    return true;
  }
  if (test === "something-special") {
    return test;
  } else {
    return false;
  }

}
Loic Duros
  • 5,472
  • 10
  • 43
  • 56
  • Asynchronous functions wont be able to return a useful value, you'll need to provide a callback function as a parameter. – zzzzBov Nov 14 '11 at 18:22
  • Why aren't you checking if the element (argument) has children before looping through them? – Headshota Nov 14 '11 at 18:25
  • Yeh in my actual function I'm doing if (n.children != undefined && n.children.length > 0) – Loic Duros Nov 14 '11 at 18:28
  • I'm still not so clear how the callback function as argument would be recursively. Not sure either how to do it. Thanks, – Loic Duros Nov 14 '11 at 18:29
  • Not sure what your function is supposed to do, and whether you indended to use variables outside of the function. The function never returns `"something-special"`, but you are checking the return value to that in the `if` statement. – pimvdb Nov 14 '11 at 18:36
  • Just edited it to return "something-special". Thanks. The idea is that there are variables outside the function scope that need only be set to true once across all of the calls to return something back at the top level of the recursive, but now if we want to use a callback to make this asynchronous, I'm not sure how that would work. – Loic Duros Nov 14 '11 at 19:01

2 Answers2

1

Using timeouts to walk the tree, seriously? Have you considered to use iterative tree traversal instead of recursive?

Example:

var walkTree = function(node) {
    var queue = [node];
    while (queue.length) {
        var n = queue.shift();
        for (var i = 0; i < n.children.length; i++) {
            queue.push(n.children[i]);
        }
        doSomethingWith(n);
    }
}

Also see this so question and wikipeida article.

Community
  • 1
  • 1
alex vasi
  • 5,304
  • 28
  • 31
  • thanks, will look into this. I've been into trying to make this recursive function work I haven't thought of looking for another way of doing it. – Loic Duros Nov 14 '11 at 19:09
  • Notice that if your tree is massive you might still want to go with an asynchronous solution in order to prevent UI freeze. – rap1ds Nov 14 '11 at 21:09
1

As alex vasi suggested, you might want to consider iterative tree traversal instead of recursive. However, if your dataset is huge and processing the data takes a lot of time, your UI may freeze. Thus, you still might want to do the processing asynchronously.

Here's a modification of alex's example:

function asyncIterativeWalkTree(node) {
    var queue = [node];

    var processQueue = function() {
        var n = queue.shift();
        for (var i = 0; i < n.children.length; i++) {
            queue.push(n.children[i]);
            setTimeout(processQueue, 0);
        }
        doSomethingWith(n);
    }

    processQueue();
}

The code snippet above does iterative traverse asynchronously, thus giving some time to the UI to update itself.

Here's a jsFiddle where you can notice the difference between synchronous and asynchronous traverse. The synchronous traverse makes your browser to freeze for a small period of time, while the asynchronous version gives browser some time to breath while processing the tree. (The code is a bit messy, sorry...)

Edit: Updated jsFiddle

rap1ds
  • 629
  • 1
  • 5
  • 10