Skip to content

Commit fe2d9a2

Browse files
vJechsmayrvJechsmayr
authored
Merge pull request vJechsmayr#58 from vitorvidaldev/vitorvidaldev
adding a binary search tree and a bfs for graph search
2 parents 5771879 + eaa6f37 commit fe2d9a2

2 files changed

Lines changed: 275 additions & 0 deletions

File tree

‎Graphs/bfs.js‎

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
/* Graphs: Breadth-first search */
2+
3+
function bfs(graph, root) {
4+
var nodesLen = {};
5+
6+
for (var i = 0; i < graph.length; i++) {
7+
nodesLen[i] = Infinity;
8+
}
9+
nodesLen[root] = 0;
10+
11+
var queue = [root];
12+
var current;
13+
14+
while(queue.length != 0) {
15+
current = queue.shift();
16+
17+
var curConnected = graph[current];
18+
var neighborIdx = [];
19+
var idx = curConnected.indexOf(i);
20+
while(idx != -1) {
21+
neighborIdx.push(idx);
22+
idx = curConnected.indexOf(1, idx + 1);
23+
}
24+
25+
for(var j = 0; j < neighborIdx.length; j++){
26+
if(nodesLen[neighborIdx[j]] == Infinity) {
27+
nodesLen[neighborIdx[j]] = nodesLen[current] + 1;
28+
queue.push(neighborIdx[j]);
29+
}
30+
}
31+
}
32+
return nodesLen;
33+
};
34+
35+
var exBFSGraph = [
36+
[0, 1, 1, 1, 0],
37+
[0, 0, 1, 0, 0],
38+
[1, 1, 0, 0, 0],
39+
[0, 0, 0, 1, 0],
40+
[0, 1, 0, 0, 0]
41+
];
42+
console.log(bfs(exBFSGraph, 1));

‎SearchAlgorithms/binarySearchTree.js‎

Lines changed: 233 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,233 @@
1+
class Node {
2+
constructor(data, left = null, right = null) {
3+
this.data = data;
4+
this.left = left;
5+
this.right = right;
6+
}
7+
}
8+
9+
class BST {
10+
constructor(){
11+
this.root = null;
12+
}
13+
add(data) {
14+
const node = this.root;
15+
if (node === null) {
16+
this.root = new Node(data);
17+
return;
18+
} else {
19+
const searchTree = function(node) {
20+
if(data < node.data) {
21+
if(node.left === null) {
22+
node.left = new Node(data);
23+
return;
24+
} else if(node.left !== null) {
25+
return searchTree(node.left);
26+
}
27+
} else if (data > node.data) {
28+
if(node.right === null) {
29+
node.right = new Node(data);
30+
return;
31+
} else if(node.right !== null) {
32+
return searchTree(node.right);
33+
}
34+
} else {
35+
return null;
36+
}
37+
};
38+
return searchTree(node);
39+
}
40+
}
41+
findMin() {
42+
let current = this.root;
43+
while (current.left !== null) {
44+
current = current.left;
45+
} return current.data;
46+
}
47+
findMax() {
48+
let current = this.root;
49+
while (current.right !== null) {
50+
current = current.right;
51+
} return current.data;
52+
}
53+
find(data) {
54+
let current = this.root;
55+
while (current.data !== data) {
56+
if(data < current.data) {
57+
current = current.left;
58+
} else {
59+
current = current.right;
60+
}
61+
if(current === null) {
62+
return null;
63+
}
64+
} return current;
65+
}
66+
isPresent(data) {
67+
let current = this.root;
68+
while (current) {
69+
if(data === current.data) {
70+
return true;
71+
}
72+
if (data < current.data) {
73+
current = current.left;
74+
} else {
75+
current = current.right;
76+
}
77+
} return false;
78+
}
79+
remove(data) {
80+
const removeNode = function(node, data) {
81+
if (node == null) {
82+
return null;
83+
}
84+
if(data == node.data) {
85+
// node has no children
86+
if(node.left == null && node.right == null){
87+
return null;
88+
}
89+
// node has no left child
90+
if(node.left == null) {
91+
return node.right;
92+
}
93+
// node has no right child
94+
if(node.right == null) {
95+
return node.left;
96+
}
97+
// node has two children
98+
var tempNode = node.right;
99+
while(tempNode.left !== null) {
100+
tempNode = tempNode.left;
101+
}
102+
node.data = tempNode.data;
103+
node.right = removeNode(node.right, tempNode.data);
104+
return node;
105+
} else if(data < node.data) {
106+
node.left = removeNode(node.left, data);
107+
return node;
108+
} else {
109+
node.right = removeNode(node.right, data);
110+
return node;
111+
}
112+
}
113+
this.node = removeNode(this.root, data);
114+
}
115+
isBalanced() {
116+
return (this.findMinHeight() >= this.findMaxHeight() - 1)
117+
}
118+
findMinHeight(node = this.root) {
119+
if(node == null) {
120+
return -1;
121+
};
122+
let left = this.findMinHeight(node.left);
123+
let right = this.findMinHeight(node.right);
124+
if(left < right) {
125+
return left + 1;
126+
} else {
127+
return right + 1;
128+
};
129+
}
130+
findMaxHeight(node = this.root) {
131+
if(node == null) {
132+
return -1;
133+
};
134+
let left = this.findMaxHeight(node.left);
135+
let right = this.findMaxHeight(node.right);
136+
if(left > right) {
137+
return left + 1;
138+
} else {
139+
return right + 1;
140+
};
141+
}
142+
inOrder() {
143+
if(this.root == null) {
144+
return null;
145+
} else {
146+
var result = new Array();
147+
function traverseInOrder(node) {
148+
node.left && traverseInOrder(node.left);
149+
result.push(node.data);
150+
node.right && traverseInOrder(node.right);
151+
}
152+
traverseInOrder(this.root);
153+
return result;
154+
};
155+
}
156+
preOrder() {
157+
if(this.root == null) {
158+
return null;
159+
} else {
160+
var result = new Array();
161+
function traversePreOrder(node) {
162+
result.push(node.data);
163+
node.left && traversePreOrder(node.left);
164+
node.right && traversePreOrder(node.right);
165+
};
166+
traversePreOrder(this.root);
167+
return result;
168+
};
169+
}
170+
postOrder() {
171+
if(this.root == null) {
172+
return null;
173+
} else {
174+
var result = new Array();
175+
function traversePostOrder(node) {
176+
node.left && traversePostOrder(node.left);
177+
node.right && traversePostOrder(node.right);
178+
result.push(node.data);
179+
};
180+
traversePostOrder(this.root);
181+
return result;
182+
}
183+
}
184+
levelOrder() {
185+
let result = [];
186+
let Q = [];
187+
if(this.root != null) {
188+
Q.push(this.root);
189+
while(Q.length > 0) {
190+
let node = Q.shift();
191+
result.push(node.data);
192+
if(node.left != null) {
193+
Q.push(node.left);
194+
};
195+
if(node.right != null) {
196+
Q.push(node.right);
197+
};
198+
};
199+
return result;
200+
} else {
201+
return null;
202+
};
203+
};
204+
}
205+
206+
const bst = new BST();
207+
208+
bst.add(4);
209+
bst.add(2);
210+
bst.add(6);
211+
bst.add(1);
212+
bst.add(3);
213+
bst.add(5);
214+
bst.add(7);
215+
bst.add(9);
216+
217+
console.log(bst.findMin());
218+
console.log(bst.findMax());
219+
console.log(bst.findMax());
220+
console.log(bst.isPresent(4));
221+
222+
console.log(bst.findMinHeight());
223+
console.log(bst.findMaxHeight());
224+
console.log(bst.isBalanced());
225+
bst.add(10);
226+
console.log(bst.findMinHeight());
227+
console.log(bst.findMaxHeight());
228+
console.log(bst.isBalanced());
229+
230+
console.log('inOrder: ' + bst.inOrder());
231+
console.log('preOrder: ' + bst.preOrder());
232+
console.log('postOrder: ' + bst.postOrder());
233+
console.log('levelOrder: ' + bst.levelOrder());

0 commit comments

Comments
 (0)