In a previous chapter, we outfitted our binary search tree with generatorbased iterability. Venturing a bit further down that rabbit hole, we note that we used breadthfirst iteration, meaning that we visited every value at the child level before moving to the grandchild level, etc.
// a breadthfirst tree traversal algorithm
var queue = this.root ? [this.root] : [];
while (queue.length > 0) {
var node = queue.shift();
yield node.value;
if (node.left) { queue.push(node.left); }
if (node.right) { queue.push(node.right); }
}
This works, but one of the cool things about BSTs is that they keep their values in sorted order. To take advantage of that, we need to switch to inorder iteration. An easy way to do that is to use recursion, which means our generator will have to call itself.
The way our tree works is that we have a Tree
class and an inner Node
class. Instances of Tree
have a root which is null if the tree is empty. Otherwise, it's an instance of Node
, which in turn can have left and right children, themselves instances of Node
, and so on.
tree

node:9
/ \
node:4 node:11
/ \ / \
null node:6 null null
We'll make both Tree
and Node
iterable, and have Tree
delegate to its root Node
, if it exists. Then the root will recursively delegate to its left and right children, if they exist, etc.
class Tree {
// ...
*[Symbol.iterator]() {
if (this.root) {
// delegate to root
for (const val of this.root) {
yield val;
}
}
}
}
class Node {
// ...
*[Symbol.iterator]() {
if (this.left) {
// delegate to this.left
for (const val of this.left) {
yield val;
}
}
yield this.value;
if (this.right) {
// delegate to this.right
for (const val of this.right) {
yield val;
}
}
}
}
This works, but we've written too much code! It turns out that generators have a much easier way to do delegation.
Generators have a special syntax to delegate to any iterable. Whenever we yield* obj
, where obj
is iterable, we inline that sequence into the sequence we're currently generating. Read yield* foo
as yield all the things in foo. Even with arbitrarilydeeply nested delegation, the consumer always sees a flat stream.
function* a() {
yield 1;
yield* arr;
yield 2;
}
var arr = [ 3, 4 ];
for (let n of a()) {
console.log(n);
}
// => 1
// => 3
// => 4
// => 2
Going back and applying this to our tree, we get this:
class Tree {
// ...
*[Symbol.iterator]() {
if (this.root) yield* this.root;
}
}
class Node {
// ...
*[Symbol.iterator]() {
if (this.left) yield* this.left;
yield this.value;
if (this.right) yield* this.right;
}
}
And voila! We have an inorder iteration over every value in the tree. There's also a gist containing a fuller example of an iterable binary search tree.
Next: Chapter VIII: Advanced topics →
Copyright © 2016 by Greg Reimer (github, twitter). Submit issues to the GitHub issues page.