2

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

enter image description here

Question:

  1. How can I change it to output the something like in the image below?
  2. 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:

enter image description here

Manish Pradhan
  • 1,141
  • 10
  • 28

2 Answers2

4

Tangled wires

Recursion and asynchrony are separate concepts but there's no reason we can't use them together. First, we'll look at some synchronous traversals then add support for asynchrony as we go. I like this style of answer because we get to see the same program represented in multiple ways. We focus on a small changes that deliver big impact.

We start with one approach using generators —

const Empty =
  Symbol ()

const breadthFirst = function* ([ node = Empty, ...nodes ])
{
  if (node === Empty)
    return
  else
    (yield node, yield* breadthFirst (nodes.concat (node.children || [])))
}

const 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" }]

for (const x of breadthFirst (data))
  console.log (x.id)
  
// 0 1 2 3 1.1 1.2 1.3 1.1.1 ... 1.1.1.1.3

Collect all the id fields in an array

const values =
  Array.from (breadthFirst (data), x => x.id)

console.log (values)
// [ '0', '1', '2', '3', '1.1', '1.2', ... '1.1.1.1.3' ]

Alternatively, we can make breadthFirst a higher-order function, much like Array.prototype.map or Array.prototype.reduce

const Empty =
  Symbol ()

const breadthFirst = (f = identity, [ node = Empty, ...nodes]) =>
  node === Empty
    ? []
    : [ f (node), ...breadthFirst (f, nodes.concat (node.children || [])) ]

const 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" }]
  
const values =
  breadthFirst (x => x.id, data)
  
console.log (values)
// [ '0', '1', '2', '3', '1.1', '1.2', ... '1.1.1.1.3' ]

We could make breadthFirst an asynchronous function using Promise

const breadthFirst = (f = identity, [ node = Empty, ...nodes]) =>
  node === Empty
    ? Promise.resolve ([])
    : breadthFirst (f, nodes.concat (node.children || [])) .then (answer => [ f (node), ...answer ])

const promiseOfValues =
  breadthFirst (x => x.id, data)

promiseOfValues.then (console.log, console.error)
// [ '0', '1', '2', '3', '1.1', '1.2', ... '1.1.1.1.3' ]

Lastly, we can make the user-supplied function f asynchronous as well

const breadthFirst = (f = identity, [ node = Empty, ...nodes]) =>
  node === Empty
    ? Promise.resolve ([])
    : Promise.resolve (node) .then (f) .then (value =>
        breadthFirst (f, nodes.concat (node.children || [])) .then (answer =>
          [ value, ...answer ]))

const promiseOfValues =
  breadthFirst (x => new Promise (r => setTimeout (r, 250, x.id)), data)

promiseOfValues.then (console.log, console.error)
// => Promise
// 4 seconds later ...
// [ '0', '1', '2', '3', '1.1', '1.2', ... '1.1.1.1.3' ]

Lastly again lol, use the new async/await syntax

const breadthFirst = async (f = identity, [ node = Empty, ...nodes]) =>
{
  if (node === Empty)
    return []

  const value =
    await Promise.resolve (node) .then (f)

  const answer =
    await breadthFirst (f, nodes.concat (node.children || []))

  return [ value, ...answer ]
}

const promiseOfValues =
  breadthFirst (x => new Promise (r => setTimeout (r, 250, x.id)), data)

promiseOfValues.then (console.log, console.error)
// => Promise
// 4 seconds later ...
// [ '0', '1', '2', '3', '1.1', '1.2', ... '1.1.1.1.3' ]

Going generic

Recursion is a functional heritage and functional programming is all about reusability. Above breadthFirst takes on many responsibilities. Beyond building the correct sequence the nodes, we need to think about the Promise API and how to wire the sequence together; this is a burden and it can be lifted. Below, we can make the process more generic using a reverse fold – unfold

const unfold = (f, init) =>
  f ( (x, next) => [ x, ...unfold (f, next) ]
    , () => []
    , init
    )

const nextLetter = c =>
  String.fromCharCode (c.charCodeAt (0) + 1)

const alphabet =
  unfold
    ( (next, done, c) =>
        c > 'z'
          ? done ()
          : next (c, nextLetter (c))
    , 'a'
    )

console.log (alphabet)
// [ a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z ]

Array.prototype.reduce takes a collection of values and reduces it to a single value – unfold takes a single value and unfolds it to a collection of values

const fib = (n = 0) =>
  unfold
    ( (next, done, [ n, a, b ]) =>
        n < 0
          ? done ()
          : next (a, [ n - 1, b, a + b ])
    , [ n, 0, 1 ]
    )

console.log (fib (20))
// [ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765 ]

OK, but you wanted asynchronous unfolding - simply add the async and await keywords

const asyncUnfold = async (f, init) =>
  f ( async (x, acc) => [ x, ...await asyncUnfold (f, acc) ]
    , async () => []
    , init
    )

Let's demo this with a less contrived function, such as an asynchronous getChildren. In a real program, this might take a node or a node id and fetch it from a database returning a Promise of the node's children. Below, we see a dramatic reduction in complexity in breadthFirst. Note the programmer is not burdened by the complexities of Promise here

const getChildren = (node) =>
  new Promise ((resolve, _) =>
    setTimeout (resolve, 250, node.children || []))

const Empty =
  Symbol ()

const breadthFirst = (nodes) =>
  asyncUnfold
    ( async (next, done, [ node = Empty, ...rest ]) =>
        node === Empty
          ? done ()
          : next (node.id, [ ...rest, ...await getChildren (node) ])
    , nodes
    )

breadthFirst (data) .then (console.log, console.error)
// => Promise
// 4 seconds later ...
// [ '0', '1', '2', '3', '1.1', '1.2', ... '1.1.1.1.3' ]

As it turns out, you didn't want a breadth-first traversal, you wanted depth-first. An advantage of the approaches used here is that we can utilize the same generic unfold function for various traversals – below we implement depthFirst identical to breadthFirst but this time we make one tiny change

const breadthFirst = (nodes) =>
const depthFirst = (nodes) =>
  asyncUnfold
    ( async (next, done, [ node = Empty, ...rest ]) =>
        node === Empty
          ? done ()
          // breadth-first
          next (node.id, [ ...rest, ...await getChildren (node) ])
          // depth-first
          : next (node.id, [ ...await getChildren (node), ...rest ])
    , nodes
    )

depthFirst (data) .then (console.log, console.error)
// => Promise
// 4 seconds later ...
// [ '0', '1', '1.1', '1.1.1', '1.1.1.1', '1.1.1.1.1', '1.1.1.1.2', ..., '2', '3' ]

remarks

A final comment about your data is a mistake that many people make when modeling hierarchical trees of data. In your data object, each item is a Node, and each item of children is a Node; however, data itself is not a Node, it is just a plain Array. This inconsistency is a pain point and actually makes your program less versatile.

Remember what I said about fold (reduce) and unfold above? reduce takes a collection and produces one value, unfold does the opposite. When traversing a tree, we start with a single node — not an array of nodes.

const breadthFirst = (nodes) =>
const breadthFirst = (node) =>
  asyncUnfold
    ( async (next, done, [ node = Empty, ...rest ]) =>
        node === Empty
          ? done ()
          : next (node.id, [ ...rest, ...await getChildren (node) ])
    , nodes
    , [ node ]
    )

const depthFirst = (nodes) =>
const depthFirst = (node) =>
  asyncUnfold
    ( async (next, done, [ node = Empty, ...rest ]) =>
        node === Empty
          ? done ()
          : next (node.id, [ ...await getChildren (node), ...rest ])
    , nodes
    , [ node ]
    )

breadthFirst ({ id: 'root', children: data }) .then (console.log, console.error)
// => Promise
// 4 seconds later ...
// [ 'root', '0', '1', '2', '3', '1.1', '1.2', ... '1.1.1.1.3' ]

depthFirst ({ id: 'root', children: data }) .then (console.log, console.error)
// => Promise
// 4 seconds later ...
// [ 'root', '0', '1', '1.1', '1.1.1', '1.1.1.1', '1.1.1.1.1', '1.1.1.1.2', ..., '2', '3' ]

Complete program demonstration

const asyncUnfold = async (f, init) =>
  f ( async (x, acc) => [ x, ...await asyncUnfold (f, acc) ]
    , async () => []
    , init
    )
    
const Empty =
  Symbol ()
  
const depthFirst = (node) =>
  asyncUnfold
    ( async (next, done, [ node = Empty, ...rest ]) =>
        node === Empty
          ? done ()
          : next (node.id, [ ...await getChildren (node), ...rest ])
    , [ node ]
    )
    
const breadthFirst = (node) =>
  asyncUnfold
    ( async (next, done, [ node = Empty, ...rest ]) =>
        node === Empty
          ? done ()
          : next (node.id, [...rest, ...await getChildren (node) ])
    , [ node ]
    )

const getChildren = (node) =>
  new Promise ((resolve, _) =>
    setTimeout (resolve, 250, node.children || []))

const 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" }]

breadthFirst ({ id: 'foo', children: data }) .then (console.log, console.error)
// => Promise
// 4 seconds later ...
// [ 'foo', '0', '1', '2', '3', '1.1', '1.2', ... '1.1.1.1.3' ]

depthFirst ({ id: 'bar', children: data }) .then (console.log, console.error)
// => Promise
// 4 seconds later ...
// [ 'bar', '0', '1', '1.1', '1.1.1', '1.1.1.1', '1.1.1.1.1', '1.1.1.1.2', ..., '2', '3' ]
Mulan
  • 129,518
  • 31
  • 228
  • 259
  • thanks but I think I made a mistake take "breadth-first" in my question, I actually wanted something like the image I just attached to the question. Sorry about that. – Manish Pradhan Mar 27 '18 at 23:29
  • @ManishPradhan your mistake opens a door for you to learn how to implement various traversals using generic functions. I've updated my answer with an edit – Mulan Mar 28 '18 at 19:49
  • 1
    Thanks to people like you :) – Manish Pradhan Apr 11 '18 at 01:51
3

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());
Mark
  • 90,562
  • 7
  • 108
  • 148