-
Notifications
You must be signed in to change notification settings - Fork 0
/
ctci-4.2-minimal-tree.js
109 lines (97 loc) · 2.55 KB
/
ctci-4.2-minimal-tree.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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
// 4.2. Minimal Tree:
// Minimal Tree: Given a sorted (increasing order) array with unique integer elements,
// write an algorithm to create a binary search tree with minimal height.
class BinaryTreeNode {
constructor(value) {
this.value = value;
this.parent = this.left = this.right = null;
}
}
class BinaryTree {
constructor(value) {
this.root = value || null;
}
//Insert a node into a BST
insert(value) {
const newNode = new BinaryTreeNode(value);
if (this.root === null) {
this.root = newNode;
} else {
let node = this.root;
let branch;
while (node) {
// nodes on the left must less than nodes on the right
branch = value <= node.value ? "left" : "right";
if (node[branch] === null) {
break;
}
node = node[branch];
}
newNode.parent = node;
node[branch] = newNode;
}
}
//Remove a node from BST
removeNode(data) {
this.root = _removeNode(this.root, data);
}
_removeNode(node, data) {
if (node === null) return null;
if (data < node.data) {
node.left = this.removeNode(node.left, key);
return node;
}
if (data > node.data) {
node.right = this.removeNode(node.right, key);
return node;
}
//if node === node.data
// current node has no children
if (node.left === null && node.right === null) {
node = null;
return node;
}
// node has one child
if (node.left === null) {
node = node.right;
return node;
}
if (node.right === null) {
node = node.left;
return node;
}
// node has two children -
// 1. Find the min value of its right subtree and use this as
// the node.
// 2. remove the min value from right subtree
let temp = this._findMinNode(node.right);
node.data = temp.data;
//remove min node from right subtree
node.right = this._removeNode(node.right, temp.data);
return node;
}
_findMinNode(node) {
if (node.left === null) return node; //this must be min node
return _findMinNode(node.left);
}
}
const createBST = (arr) => {
let tree = new BinaryTree();
if (arr && arr.length) {
addNode(tree, arr, 0, arr.length - 1);
}
console.log(tree);
return tree;
};
function addNode(tree, arr, start, end) {
if (start === end) {
tree.insert(arr[start]);
}
if (start < end) {
let mid = start + parseInt((end - start) / 2);
tree.insert(arr[mid]);
addNode(tree, arr, start, mid - 1);
addNode(tree, arr, mid + 1, end);
}
}
createBST([1, 2, 3, 4, 5, 6, 7]);