In this blog post we are going to take a look at how could be implemented iterator of binary search tree using the ES6 generators.
Initially I’m going to tell a few words about how generators could be used, after that we will look at the iterator design patterns and last, but not least we are going to take a look at the BST (binary search tree) iterator implementation.
Once we have defined given generator, we can instantiate it (more preciously we create an iterator) by simply invoking it like a function:
Ok, so far we know how to define generators and instantiate them. The interesting part comes when we include the keyword
yield into the game. With
yield we can suspend the execution of the current generator and change the control flow:
Initially we create a new instance of the generator and pass Pi as parameter. Later with
yield 42 we suspend the execution of the generator. By calling the
next method we restore the execution from the last suspension point. By passing argument to
next we can get value from the outside of the generator (like in
var returnRes = yield param).
So far so good, but some times we want to pass the execution to another generator. For this case we have a special syntax -
Iterator Design Pattern
The iterator pattern belongs to the behavioral design patterns. It is used with collections of objects and its main aim is separation of the logic for traversing given collection, from the actual collection’s implementation.
Big advantage of this design pattern is that the abstract
Iterator class provides common interface, which could be later implemented by multiple
ConcreteIterators. This way we can traverse different collections (BSTs, linked lists, hash maps, etc.) using the same interface provided by the collection’s iterator.
In this article we are going to extend the BST’s API by adding a method called
Here is its implementation:
In the snippet above, we create new instance of
BinarySearchTreeIterator by passing the current BST instance and after that invoking it’s
next method. The
next method of the iterator will return the next element of the collection. Initially, during the creation of the iterator, we need to call it because the
next method is actually a generator, so by invoking it we return new instance of the generator.
Here is the implementation of the iterator:
You can see that the only difference between the in-order traverse of the BST using iterator and the one implemented in the BST, is that the iterator uses
yield syntax is used depending on whether we want to suspend the execution or to “redirect” it to different generator instead.
Here is how our iterator could be used: