-
Notifications
You must be signed in to change notification settings - Fork 10
Expand file tree
/
Copy pathBinarySearchTree.js
More file actions
148 lines (133 loc) · 4.08 KB
/
BinarySearchTree.js
File metadata and controls
148 lines (133 loc) · 4.08 KB
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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
/**
* Created by youngsug on 5/15/2016.
*/
var Node = function(data) {
this.value = data;
this.left = null;
this.right = null;
return this;
};
function BinarySearchTree() {
this._root = null;
}
BinarySearchTree.prototype.add = function(value){
//create a new item object, place data in
var node = new Node(value);
//used to traverse the structure current;
//special case: no items in the tree yet
if (this._root === null){
this._root = node;
} else {
var current = this._root;
while(true){
//if the new value is less than this node's value, go left
if (value < current.value){
//if there's no left, then the new node belongs there
if (current.left === null){
current.left = node;
break;
} else {
current = current.left;
}
//if the new value is greater than this node's value, go right
} else if (value > current.value){
//if there's no right, then the new node belongs there
if (current.right === null){
current.right = node;
break;
} else {
current = current.right;
}
//if the new value is equal to the current one, just ignore
} else {
break;
}
}
}
};
BinarySearchTree.prototype.contains = function(value){
var found = false,
current = this._root
//make sure there's a node to search
while(!found && current){
//if the value is less than the current node's, go left
if (value < current.value){
current = current.left;
//if the value is greater than the current node's, go right
} else if (value > current.value){
current = current.right;
//values are equal, found it!
} else {
found = true;
}
}
//only proceed if the node was found
return found;
};
BinarySearchTree.prototype.traverse = function(process, order){
//helper function
function inOrder(node){ // sort - default
if (node){
//traverse the left subtree
if (node.left !== null){
inOrder(node.left);
}
//call the process method on this node
process.call(this, node);
//traverse the right subtree
if (node.right !== null){
inOrder(node.right);
}
}
}
function preOrder(node){
if (node){
//call the process method on this node
process.call(this, node);
//traverse the left subtree
if (node.left !== null){
preOrder(node.left);
}
//traverse the right subtree
if (node.right !== null){
preOrder(node.right);
}
}
}
function postOrder(node){
if (node){
//traverse the left subtree
if (node.right !== null){
postOrder(node.right);
}
//call the process method on this node
process.call(this, node);
//traverse the right subtree
if (node.left !== null){
postOrder(node.left);
}
}
}
//start with the root
if(order =='pre') {
preOrder(this._root);
}else if(order =='post'){
postOrder(this._root);
}else{
inOrder(this._root);
}
};
BinarySearchTree.prototype.size = function(order){
var length = 0;
this.traverse(function(node){
length++;
}, order);
return length;
};
BinarySearchTree.prototype.toArray = function(order){
var result = [];
this.traverse(function(node){
result.push(node.value);
}, order);
return result;
};