Generators & Depth First Search (DFS)

ES6 Generators

So, the way I like to learn things is combining the thing I want to learn with real world use cases. Too many times, concepts/ideas, are coupled with learning approaches that never stick because they are coupled with examples that are never used. Thus, concepts are not solidified or even justified.

So, lets take a stab at Generators and a Depth First Search (DFS). Now, in all my years of programming I’ve never had to do a DFS. That isn’t to say this exercise isn’t useful. Many interviews have a DFS question, and DFS is solidified in the lexicon of programming that it does satisfy our “real use case”.

So, what is a Depth First Search?
DFS is an algorithm for traversing or searching, tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking. ( — wikipedia )

How would that look in practice?

So, given the definition above and our image to our left, we can get a better understanding of how a DFS works. We start at the topmost node (1 in this case), and we move left down (in this example) as far as we can go (3, in this example) etc.. But, lets just write out the path sequence:
1, 2, 3, 2, 4, 2, 1, 5, 6, 5, 7

That can be a little confusing, but if we think of the idea that we go as far as we can, then backtrack, then take any branches that exist (bolded above — new nodes).

So, we can backtrack along nodes we previously visited to then find new nodes.

Now that we have an idea of what a DFS looks like — lets move on to how we can implement a DFS with Generators. I will need to assume you have an understanding of Generators already. Now, as I move thru the code example, I will be explicit on what I am doing and what is going on, I just will assume you can bridge the flow with your current understanding. Btw, you can always ping me thru email, and I will be more than happy to explain in detail, anything further.

Cool, lets get started.

Lets create our Tree class. I will give it all upfront, then we will dissect it.

class Tree {
  constructor(value = null, children = []) {
    this.value = value;
    this.children = children
  }
// Depth First Solution
*printValues() {
  yield this.value;
  for(let child of this.children) {
    yield* child.printValues();
  }
 }
}
// DEPTH first
// See explanations below for a bit more succinct way to 
// generate this tree.
const tree = 
  new Tree(1, [
    new Tree(2, [
       new Tree(5, [
         new Tree(9),
         new Tree(10)
       ]),
       new Tree(6)
     ]),
    new Tree(3),
    new Tree(4, [
       new Tree(7, [
          new Tree(11), 
          new Tree(12)
        ] ), 
        new Tree(8)])
])
const values = []
for(let value of tree.printValues()) {
  values.push(value);
}
values
// our results are:
// [1, 2, 5, 9, 10, 6, 3, 4, 7, 11, 12, 8]

Now, I created a simple/general Class Tree (please keep in mind that a Class is not a requirement.)

Our data structure is just a view on parent -> child relationships. We can change those up (I do later), but lets visit our code. I will just give a brief explanation of what is happening in the constructor, as that is not really the focus of this story.

constructor(value = null, children = []) {
    this.value = value;
    this.children = children
  }

Just see this as a function that takes two arguments, a value, and children.
If we compare this function signature (ie.. ‘arity’ or ‘number of arguments’), it fits nicely with:

new Tree(5, [new Tree(9),new Tree(10)])
this.value = 5;
this.children = [new Tree(9),new Tree(10)]
As you can see, the children is an array of "Tree's", that have their own "value" and "children". 

Lets move onto our “printValues()” method, this is where our generator magic happens.

*printValues() {
  yield this.value;
for(let child of this.children) {
    yield* child.printValues();
  }
 }

What do we notice here? “*”
What the heck is that? That is how we denote a “generator” function, by apply an asterick to it.

*printValues() {
  yield this.value;
1. yield - The yield keyword is used to pause and resume a generator function.
2. Here we are "yielding" out this.value, for our current 'this' context. If this was the first iteration of our tree: new Tree(1, then our value is 1. Based on our explanation (see #1), at this point we pause. So, we yielded out 1, now what?

Here is our second code snippet. Now that we have paused after yielded out a 1. Our second second here is the resume aspect of our generator. We will get into “how” we resume, further down. But lets assume, for now, we resume on and hit this part of the code.

for(let child of this.children) {
    yield* child.printValues();
  }
 }
// Here are some other ways to show the data rather than calling 
// 'new Tree' inline everywhere. We can create a helper function
// to recursively go thru everything.
const tree = {
  1: { 
    2: {
       5: {
         9: {},
         10: {},
       6: {}
    },
    3: {},
    4: {
       7: {
         11: {},
         12: {}
        }, 
       8: {}
    }
  }
}
}
const tree = [1,[ 2,[5, [9,10],6,3,4,7,[ 11, 12],8]]]

OOPS: didn’t realize I hand’t finished this story. :-( , will update shortly.