Skip to content

Instantly share code, notes, and snippets.

@hbarcelos
Created September 24, 2016 16:26
Show Gist options
  • Save hbarcelos/26110bc9472cdd41e1a9dbbd4533c23f to your computer and use it in GitHub Desktop.
Save hbarcelos/26110bc9472cdd41e1a9dbbd4533c23f to your computer and use it in GitHub Desktop.
Tree iterators using ES6 generators
class BinaryTree {
constructor(value, left=null, right=null) {
this.value = value
this.left = left
this.right = right
}
}
class InOrderIterator extends TreeIterator {
* [Symbol.iterator] () {
if (this.tree.left)
yield* new InOrderIterator(this.tree.left)
yield this.tree.value
if (this.tree.right)
yield* new InOrderIterator(this.tree.right)
}
}
class PostOrderIterator extends TreeIterator {
* [Symbol.iterator] () {
if (this.tree.left)
yield* new PostOrderIterator(this.tree.left)
if (this.tree.right)
yield* new PostOrderIterator(this.tree.right)
yield this.tree.value
}
}
class PreOrderIterator extends TreeIterator {
* [Symbol.iterator] () {
yield this.tree.value
if (this.tree.left)
yield* new PreOrderIterator(this.tree.left)
if (this.tree.right)
yield* new PreOrderIterator(this.tree.right)
}
}
const tree = new BinaryTree('a',
new BinaryTree('b',
new BinaryTree('c'),
new BinaryTree('d')),
new BinaryTree('e'));
const preOrderIt = new PreOrderIterator(tree)
const inOrderIt = new InOrderIterator(tree)
const postOrderIt = new PostOrderIterator(tree)
console.log([...preOrderIt]) // [ 'a', 'b', 'c', 'd', 'e' ]
console.log([...inOrderIt]) // [ 'c', 'b', 'd', 'a', 'e' ]
console.log([...postOrderIt]) // [ 'c', 'd', 'b', 'e', 'a' ]
class TreeIterator {
constructor(tree) {
this.tree = tree
}
* [Symbol.iterator] () {
throw new Error('Not implemented')
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment