-
Notifications
You must be signed in to change notification settings - Fork 0
/
delete-node-bst.js
73 lines (67 loc) · 1.7 KB
/
delete-node-bst.js
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {number} key
* @return {TreeNode}
*/
let noChild = (parent, key) => {
if (key > parent.val) {
parent.right = null;
} else {
parent.left = null;
}
};
let oneChild = (node) => {
if (node.left) {
let left = node.left;
node.val = left.val;
node.left = left.left;
node.right = left.right;
} else if (node.right) {
let right = node.right;
node.val = right.val;
node.right = right.right;
node.left = right.left;
}
};
let twoChildren = (node, rightParent, right) => {
if (right.left) {
return twoChildren(node, right, right.left);
}
if (node.val === rightParent.val) {
node.right = rightParent.right.right;
} else {
rightParent.left = right.right;
}
node.val = right.val;
};
let del = (node, parent, val) => {
if (!node) return;
if (node.val === val) {
if (!node.left && !node.right) {
noChild(parent, val);
} else if ((node.left && !node.right)
|| !node.left && node.right) {
oneChild(node);
} else if (node.left && node.right) {
twoChildren(node, node, node.right);
}
return;
}
if (node.val > val) return del(node.left, node, val);
if (node.val < val) return del(node.right, node, val);
};
let deleteNode = (root, key) => {
if (root && !root.left && !root.right && root.val === key) {
return null;
}
del(root, root, key);
return root;
};
export default deleteNode;