/
index.ts
53 lines (48 loc) · 1.58 KB
/
index.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import { TreeNode } from "../binary-tree-inorder-traversal/TreeNode.ts";
export function* InOrderIterator(root: TreeNode | null): Generator<number> {
if (!root) return;
yield* InOrderIterator(root.left);
yield (root.val);
yield* InOrderIterator(root.right);
}
class BSTIterator {
#gen: Generator<number, void, unknown>;
#result: IteratorResult<number, void>;
#list: TreeNode | null = null;
constructor(root: TreeNode | null) {
this.#gen = InOrderIterator(root);
this.#result = this.#gen.next();
}
next(): number {
if (this.#list === null) {
const value = this.#result.value;
if (typeof value === "undefined") return Infinity;
this.#list = new TreeNode(value);
this.#result = this.#gen.next();
return value;
}
if (this.#list?.right) {
this.#list = this.#list.right;
return this.#list.val;
} else {
const value = this.#result.value;
if (typeof value === "undefined") return Infinity;
this.#result = this.#gen.next();
const node = new TreeNode(value, this.#list);
this.#list.right = node;
this.#list = node;
return value;
}
}
hasNext(): boolean {
return !!(this.#list?.right || !this.#result.done);
}
prev(): number {
if (this.#list?.left) this.#list = this.#list.left;
return this.#list?.val ?? -Infinity;
}
hasPrev(): boolean {
return !!(this.#list?.left);
}
}
export default BSTIterator;