TypeScriptbst.ts
Copy
1
class TreeNode {
2
  constructor(
3
    public val: number,
4
    public left: TreeNode | null = null,
5
    public right: TreeNode | null = null
6
  ) {}
7
}
8
 
9
class BST {
10
  root: TreeNode | null = null;
11
 
12
  insert(val: number): void {
13
    this.root = this._insert(this.root, val);
14
  }
15
 
16
  private _insert(node: TreeNode | null, val: number): TreeNode {
17
    if (!node) return new TreeNode(val);
18
    if (val < node.val) node.left = this._insert(node.left, val);
19
    else if (val > node.val) node.right = this._insert(node.right, val);
20
    return node;
21
  }
22
 
23
  search(val: number): boolean {
24
    let curr = this.root;
25
    while (curr) {
26
      if (val === curr.val) return true;
27
      curr = val < curr.val ? curr.left : curr.right;
28
    }
29
    return false;
30
  }
31
 
32
  inOrder(): number[] {
33
    const result: number[] = [];
34
    const traverse = (node: TreeNode | null) => {
35
      if (!node) return;
36
      traverse(node.left);
37
      result.push(node.val);
38
      traverse(node.right);
39
    };
40
    traverse(this.root);
41
    return result;
42
  }
43
 
44
  height(): number {
45
    const h = (node: TreeNode | null): number =>
46
      node ? 1 + Math.max(h(node.left), h(node.right)) : 0;
47
    return h(this.root);
48
  }
49
}
50
 
51
const bst = new BST();
52
[5, 3, 7, 1, 4, 6, 8].forEach(v => bst.insert(v));
53
console.log(bst.inOrder());    // [1, 3, 4, 5, 6, 7, 8]
54
console.log(bst.search(4));    // true
55
console.log(bst.height());     // 3