Recursive JS function with setTimeout

Question

I have the following code

var data = [
  { id: "0" },
  {
    id: "1",
    children: [
      {
        id: "1.1",
        children: [
          {
            id: "1.1.1",
            children: [
              {
                id: "1.1.1.1",
                children: [
                  { id: "1.1.1.1.1" },
                  { id: "1.1.1.1.2" },
                  { id: "1.1.1.1.3" }
                ]
              },
              { id: "1.1.1.2" },
              { id: "1.1.1.3" }
            ]
          },
          { id: "1.1.2" },
          { id: "1.1.3" },
        ]
      },
      { id: "1.2" },
      { id: "1.3" }
    ]
  },
  { id: "2" },
  { id: "3" }
];

function recursive(current) {
  var first = current[0];
  current.shift();
  var remaining = current;

  console.log(first.id);

  if (first.children) {
    setTimeout(function(){
      recursive(first.children);
    })
  }

  if (remaining.length) {
    setTimeout(function(){
      recursive (remaining);
    });
  }
}

recursive(data);

This output is not in order because of the setTimeout

Question:

How can I change it to output the something like in the image below?
How do I know the last iteration in this recursive function? I need to run something once the list is exhausted.

I cant use forEach because I have to use setTimeouts for a different reason. I understand setTimeout does not work properly in a loop. Any ideas????

Desired output:

Mark · Accepted Answer

Generally speaking when you want to do breadth-first iteration, you need to use a queue (ie. FIFO). Javascript doesn't have a native queue data structure, so this just uses an array and shift, but it still gets the job done.

Here you just push everything into the queue at each level. This insures the children get pushed in after the parents, and therefore you iterate over the parents first. Normally with a graph you would also keep track of where you've been, but since this is a tree, there are no loops.

var data = [ { id: "0" }, { id: "1", children: [ { id: "1.1", children: [ { id: "1.1.1", children: [ { id: "1.1.1.1", children: [ { id: "1.1.1.1.1" }, { id: "1.1.1.1.2" }, { id: "1.1.1.1.3" } ] }, { id: "1.1.1.2" }, { id: "1.1.1.3" } ] }, { id: "1.1.2" }, { id: "1.1.3" }, ] }, { id: "1.2" }, { id: "1.3" } ] }, { id: "2" }, { id: "3" } ];

function recursive(queue) {
  var current = queue.shift();
  if (current === undefined) return
  console.log(current.id)
  if (current.children) {
    current.children.forEach(node => {
      queue.push(node)
    })
  }
  setTimeout(function() {
    recursive(queue)
  })
}

recursive(data);

EDIT - FOR DEPTH FIRST:

If you want depth first you basically use a stack rather than a queue. Here it's a little strange because you care about the order of the children, so we load the stack backwards.

var data = [ { id: "0" }, { id: "1", children: [ { id: "1.1", children: [ { id: "1.1.1", children: [ { id: "1.1.1.1", children: [ { id: "1.1.1.1.1" }, { id: "1.1.1.1.2" }, { id: "1.1.1.1.3" } ] }, { id: "1.1.1.2" }, { id: "1.1.1.3" } ] }, { id: "1.1.2" }, { id: "1.1.3" }, ] }, { id: "1.2" }, { id: "1.3" } ] }, { id: "2" }, { id: "3" } ];
  
function recursive(stack) {
    let current = stack.pop()
    if (current === undefined) return
    console.log(current.id)
    if(current.children)  {
        stack.push(...current.children.reverse())
    }
    setTimeout(function(){
        recursive(stack)
    })
}
recursive(data.reverse());

Recursive JS function with setTimeout

Answers (2)

Related Questions