I am trying to solve this leetcode question https://leetcode.com/problems/binary-search-tree-iterator/ where it asks you to make an iterate to traverse the BST and I thought generators are a good fit for it.
Here is my attempt
class BSTIterator {
constructor(root) {
this.root = root
this._gen = this._getGen(root)
}
*_getGen(node) {
if(node) {
yield* this._getGen(node.left)
yield node.val
yield* this._genGen(node.right)
}
}
next() {
return this._gen.next().value
}
hasNext() {
return this._gen.next().done
}
}
But I got an error saying
TypeError: yield* is not a terable
Can someone help me understand where I did wrong and what are the correct solutions to this problem by using generators?
A few issues:
yield* this._genGen(node.right)... change it to get with a t.done will have the opposite boolean value from what hasNext should return, so you need to negate thatdone is when already having done a .next() call on the iterator. So you need the iterator to always be one step ahead, and remember its return value in the state of your instance.So here is how you can change your code:
class BSTIterator {
constructor(root) {
this.root = root;
this._gen = this._getGen(root);
// Already call `next()`, and retain the returned value
this.state = this._gen.next();
}
*_getGen(node) {
if (node) {
yield* this._getGen(node.left);
yield node.val;
yield* this._getGen(node.right); // fix typo
}
}
next() {
let {value} = this.state; // This has the value to return
this.state = this._gen.next(); // Already fetch next
return value;
}
hasNext() {
// Get `done` from the value already retrieved, and invert:
return !this.state.done;
}
}