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
54
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;