Binary Search Tree (BST)

1class TreeNode {
2  constructor(val) {
3    this.val = val;
4    this.left = null;
5    this.right = null;
6  }
7}
8 
9class BinarySearchTree {
10  constructor() {
11    this.root = null;
12  }
13 
14  insert(val) {
15    const newNode = new TreeNode(val);
16    if (!this.root) {
17      this.root = newNode;
18      return this;
19    }
20    let current = this.root;
21    while (true) {
22      if (val === current.val) return undefined;
23      if (val < current.val) {
24        if (!current.left) {
25          current.left = newNode;
26          return this;
27        }
28        current = current.left;
29      } else {
30        if (!current.right) {
31          current.right = newNode;
32          return this;
33        }
34        current = current.right;
35      }
36    }
37  }
38 
39  search(val) {
40    let current = this.root;
41    while (current) {
42      if (val === current.val) return true;
43      current = val < current.val ? current.left : current.right;
44    }
45    return false;
46  }
47 
48  inOrderTraversal(node = this.root, result = []) {
49    if (node) {
50      this.inOrderTraversal(node.left, result);
51      result.push(node.val);
52      this.inOrderTraversal(node.right, result);
53    }
54    return result;
55  }
56}