Depth First Traversing using Generators in Javascript

Imagine you are having a tree structured object as shown below and you would like to traverse through each node and print it’s name.

{
    _id: 1,
    name: "Root Node",
    ...otherFields,
    children: [
        {
            _id: 2,
            name: "Child 1",
            ...otherFields
        },
        {
            _id: 3,
            name: "Child 2",
            ...otherFields,
            children: [
                {
                    _id: 2,
                    name: "Grandchild",
                    ...otherFields
                }
            ]
        },
        {
            _id: 4,
            name: "Child 3",
            ...otherFields
        }
    ]
}

How can we acheive this? Well this problem is called Tree Traversing and they are age old ones. What if we can loop through the nodes of a tree just like an array? Javascript has generator functions which can emit values that can be consumed by for..of loops.

Let us create a Depth-First iterator with the following generator function. Depth First Traversal (DFS) is a traversing technique where we traverse from the Root node.

function* dfs(node) {
  yield node;
  if (Array.isArray(node.children)) {
    for (let child of node.children) {
      yield* dfs(child);
    }
  }
}

Notice the yield* in the function. This is necessary if we want to yield a value which is returned by a recursive call.

Now you just have to pass the root node to this generator function.

for(const node of dfs(rootNode)) {
    console.log(node.name)
}

This does lazy traversing, which means it doesn’t do all the traversing at once, it executes till it reaches the first yield statement and then executes the first iteration of the loop. On every execution of yield statement it returns the next value to the iterator. This is pretty useful when you want to skip nodes based on some logic while traversing. To achieve this lazy behavior without generators, you have to pass a callback through the recursive calls which has to be executed for each node. Thankfully generators make the code look like sequential execution and yet keeps it lazy.

This is very useful when you want to render a tree in the UI as an unordered list with CSS to make it appear like a tree.