Turning recursive node traversal into iterative node traversal

Question

I have a recursive algorithm for traversing nodes in a document tree in tree order

How would this be made iterative? My attempt at making it iterative completely failed

function recursivelyWalk(nodes, cb) {
    for (var i = 0, len = nodes.length; i < len; i++) {
        var node = nodes[i],
            ret = cb(node)

        if (ret) {
            return ret
        }

        if (node.childNodes.length) {
            var ret = recursivelyWalk(node.childNodes, cb)
            if (ret) {
                return ret
            }
        }
    }
}

@SaeedAmiri might mean queue. What is the reason you're trying to avoid recursion here? — Jordan Running
– Jordan Running, Commented Mar 3, 2012 at 19:35
@Jordan one avoids recursion due to lack of tail call optimisation — Raynos
– Raynos, Commented Mar 3, 2012 at 19:59

pimvdb · Accepted Answer · 2012-03-03 19:56:55Z

2

What about concatenating the child nodes if there are any, and using a while(nodes.length) loop? Basically, keep adding new nodes to the stack, and keep running the loop (testing one node each time) until the stack is empty: http://jsfiddle.net/gEm77/1/.

var z = 0; // my precaution for a while(true) loop

function iterativelyWalk(nodes, cb) {
    nodes = [].slice.call(nodes);

    while(++z < 100 && nodes.length) {
        var node = nodes.shift(),
            ret = cb(node);

        if (ret) {
            return ret;
        }

        if (node.childNodes.length) {
            nodes = [].slice.call(node.childNodes).concat(nodes);
        }
    }
}

edited Mar 3, 2012 at 19:56

answered Mar 3, 2012 at 19:37

pimvdb

155k80 gold badges313 silver badges358 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Raynos Over a year ago

That would work if it was changed to enforce tree order. nodes = [].slice.call(node.childNodes).concat(nodes) should preserve tree order

pimvdb Over a year ago

@Raynos: Good call; edited. The new nodes should indeed be pushed to the beginning of the array due to .shift().

Jordan Running · Accepted Answer · 2012-03-03 19:50:15Z

2

This article (linked from Wikipedia's article on tree traversal) gives an algorithm in JavaScript for iterative preorder traversal of a DOM tree. To quote:

function preorderTraversal(root) {
  var n = root;
  while(n) {
  // If node have already been visited
    if (n.v) {
      // Remove mark for visited nodes
      n.v = false;
      // Once we reach the root element again traversal
      // is done and we can break
      if (n == root)
        break;
      if (n.nextSibling)
        n = n.nextSibling;
      else
        n = n.parentNode;
    }
    // else this is the first visit to the node
    else {
      //
      // Do something with node here...
      //
      // If node has childnodes then we mark this node as
      // visited as we are sure to be back later
      if (n.firstChild) {
        n.v = true;
        n = n.firstChild;
      }
      else if (n.nextSibling)
        n = n.nextSibling;
      else
        n = n.parentNode;
    }
  }
}

Note the line "// Do something with node here...", which is where you can call your callback function.

Check out the full article for more information.

answered Mar 3, 2012 at 19:50

Jordan Running

107k18 gold badges193 silver badges189 bronze badges

1 Comment

Raynos Over a year ago

That's an ugly implementation

Collectives™ on Stack Overflow

Turning recursive node traversal into iterative node traversal

2 Answers 2

2 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related