-
Notifications
You must be signed in to change notification settings - Fork 15
/
bst.js
110 lines (95 loc) · 2.57 KB
/
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
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
110
// Binary Search Tree
// binary search tree constructor
function BST(value) {
this.value = value
this.right = null
this.left = null
}
// insertion function
BST.prototype.insert = function(value) {
if (value <= this.value) {
if (!this.left) this.left = new BST(value)
else this.left.insert(value)
}
else if (value > this.value) {
if (!this.right) this.right = new BST(value)
else this.right.insert(value)
}
}
// binary search function
BST.prototype.contains = function(value) {
if (this.value === value) return true
if (value < this.value) {
if (!this.left) return false
else return this.left.contains(value)
}
else if (value > this.value) {
if (!this.right) return false
else return this.right.contains(value)
}
}
// depth first traversal in order, pre-order, post-order
BST.prototype.depthFirstTraversal = function(iteratorFunc, order) {
if (this.order === 'pre-order') iteratorFunc(this.value)
if (this.left) this.left.depthFirstTraversal(iteratorFunc, order)
if (order === 'in-order') iteratorFunc(this.value)
if (this.right) this.right.depthFirstTraversal(iteratorFunc, order)
if (order === 'post-order') iteratorFunc(this.value)
}
// breadth first traversal
BST.prototype.breadthFirstTraversal = function(iteratorFunc) {
// start the queue with the root node aka this
let queue = [this]
// while loop runs as long as queue is not empty
while (queue.length) {
// take node out of queue, and work on it with iteratorFunc
let treeNode = queue.shift()
iteratorFunc(treeNode)
// if the node has left or right child, push them into the queue
if (treeNode.left) queue.push(treeNode.left)
if (treeNode.right) queue.push(treeNode.right)
}
}
// traverse tree recursively and extract min val
BST.prototype.getMinVal = function() {
if (!this.left) {
return this.value
}else{
return this.left.getMinVal()
}
}
// traverse tree recursively and extract max val
BST.prototype.getMaxVal = function() {
if (!this.right) {
return this.value
}else{
return this.right.getMaxVal()
}
}
// invert binary tree
let invertBinTree = tree => {
if (tree === null){
return null
}
leftInvert = invertBinTree(tree.left)
rightInvert = invertBinTree(tree.right)
let temp = tree.left
tree.left = tree.right
tree.right = temp
return tree
}
let log = (value) => {
console.log(value)
}
let bst = new BST(50);
bst.insert(30);
bst.insert(70);
bst.insert(100);
bst.insert(60);
bst.insert(59);
bst.insert(20);
bst.insert(45);
bst.insert(35);
bst.insert(85);
bst.insert(105);
bst.insert(10);