1class Node {
2  constructor(val) {
3    this.data = val;
4    this.left = null;
5    this.right = null;
6  }
7}
8
9class BST {
10  constructor() {
11    this.root = null;
12  }
13  insert(val) {
14    const newNode = new Node(val);
15    if (!this.root) {
16      this.root = newNode;
17      return;
18    }
19    let current = this.root;
20    while (current) {
21      if (val < current.data) {
22        if (!current.left) {
23          current.left = newNode;
24          return;
25        }
26        current = current.left;
27      } else if (val > current.data) {
28        if (!current.right) {
29          current.right = newNode;
30          return;
31        }
32        current = current.right;
33      } else {
34        return;
35      }
36    }
37  }
38
39  printInOrder(node = this.root) {
40    if (!node) return [];
41    return [...this.printInOrder(node.left), node.data, ...this.printInOrder(node.right)];
42  }
43  delete(node = this.root, val) {
44    if (!node) {
45      return null;
46    }
47    if (node.data === val) {
48      return this.helper(node);
49    }
50
51    let current = node;
52    while (current) {
53      if (current.data > val) {
54        if (current.left && current.left.data === val) {
55          current.left = this.helper(current.left);
56          break;
57        } else {
58          current = current.left;
59        }
60      } else {
61        if (current.right && current.right.data === val) {
62          current.right = this.helper(current.right);
63          break;
64        } else {
65          current = current.right;
66        }
67      }
68    }
69    return current;
70  }
71
72  helper(node) {
73    if (!node.left) {
74      return node.right;
75    } else if (!node.right) {
76      return node.left;
77    }
78    let rightChild = node.right;
79    let lastRightChildOfLeft = this.findLastRightChild(node.left);
80    lastRightChildOfLeft.right = rightChild;
81    return node.left;
82  }
83  findLastRightChild(node) {
84    if (!node.right) {
85      return node;
86    }
87    return this.findLastRightChild(node.right);
88  }
89}
90const bst = new BST();
91bst.insert(5);
92bst.insert(2);
93bst.insert(8);
94bst.insert(1);
95bst.insert(3);
96console.log(bst.printInOrder());
97bst.delete(bst.root, 3);
98console.log(bst.printInOrder());
99bst.delete(bst.root, 2);
100console.log(bst.printInOrder());
101bst.delete(bst.root, 1);
102console.log(bst.printInOrder());
103