iterative-dfs.js

// Iterative depth first search
function IterativeDFSTraversal(root, fn, fnArgs) {
  var stack = [], nodeIdx = [], stackFrameArgs = [];
  
  fnArgs = fn(root, fnArgs);
  
  if (fnArgs) {
    stack.push(root);
    nodeIdx.push(0);
    stackFrameArgs.push(fnArgs);
  }
  
  while (stack.length > 0) {
    var current = stack[stack.length - 1];
    var currentNodeIdx = nodeIdx[stack.length - 1];
    fnArgs = stackFrameArgs[stack.length - 1];
    
    if (currentNodeIdx >= current.children.length) {
      
      stack.pop();
      nodeIdx.pop();
      
    } else {
      
      fnArgs = fn(current.children[currentNodeIdx], fnArgs);
      if (fnArgs) {
        stack.push(current.children[currentNodeIdx]);
        nodeIdx.push(0);
        stackFrameArgs.push(fnArgs);
      }
      nodeIdx[stack.length - 1] = currentNodeIdx + 1;
      
    }
  }
}