algorithms/delete_bst_node.js at main · msfreemind/algorithms · GitHub

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
var deleteNode = function(root, key) {
  let prevNode, node = root;

  while (node) {
    if (key < node.val) {
      prevNode = node;
      node = node.left;
    } else if (key > node.val) {
      prevNode = node;
      node = node.right;
    } else {
      if (node.left && node.right) {
        let traversalNode = node.right;

        while (traversalNode.left) traversalNode = traversalNode.left;

        traversalNode.left = node.left;
        node.left = null;
      }

      if (prevNode) {
        if (node.val < prevNode.val) prevNode.left = node.right || node.left;
        else prevNode.right = node.right || node.left;
      } else {
        node = node.right || node.left;
      }

      break;
    }
  }

  if (prevNode) return root;
  else return node;
};