JavaScript/Data-Structures/Tree/BinarySearchTree.js at master · flexycode/JavaScript · GitHub

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
149
150
151
152
153
154
/* Binary Search Tree!!
 *
 * Nodes that will go on the Binary Tree.
 * They consist of the data in them, the node to the left, the node
 * to the right, and the parent from which they came from.
 *
 * A binary tree is a data structure in which an element
 * has two successors(children). The left child is usually
 * smaller than the parent, and the right child is usually
 * bigger.
 */

// class Node
constNode=(functionNode(){
// Node in the tree
functionNode(val){
this.value=val
this.left=null
this.right=null
}

// Search the tree for a value
Node.prototype.search=function(val){
if(this.value===val){
returnthis
}elseif(val<this.value&&this.left!==null){
returnthis.left.search(val)
}elseif(val>this.value&&this.right!==null){
returnthis.right.search(val)
}
returnnull
}

// Visit a node
Node.prototype.visit=function(output=(value)=>console.log(value)){
// Recursively go left
if(this.left!==null){
this.left.visit()
}
// Print out value
output(this.value)
// Recursively go right
if(this.right!==null){
this.right.visit()
}
}

// Add a node
Node.prototype.addNode=function(n){
if(n.value<this.value){
if(this.left===null){
this.left=n
}else{
this.left.addNode(n)
}
}elseif(n.value>this.value){
if(this.right===null){
this.right=n
}else{
this.right.addNode(n)
}
}
}

// remove a node
Node.prototype.removeNode=function(val){
if(val===this.value){
if(!this.left&&!this.right){
returnnull
}else{
if(this.left){
constleftMax=maxVal(this.left)
this.value=leftMax
this.left=this.left.removeNode(leftMax)
}else{
constrightMin=minVal(this.right)
this.value=rightMin
this.right=this.right.removeNode(rightMin)
}
}
}elseif(val<this.value){
this.left=this.left&&this.left.removeNode(val)
}elseif(val>this.value){
this.right=this.right&&this.right.removeNode(val)
}
returnthis
}

// find maximum value in the tree
constmaxVal=function(node){
if(!node.right){
returnnode.value
}
returnmaxVal(node.right)
}

// find minimum value in the tree
constminVal=function(node){
if(!node.left){
returnnode.value
}
returnminVal(node.left)
}
// returns the constructor
returnNode
})()

// class Tree
constTree=(function(){
functionTree(){
// Just store the root
this.root=null
}

// Inorder traversal
Tree.prototype.traverse=function(){
if(!this.root){
// No nodes are there in the tree till now
return
}
this.root.visit()
}

// Start by searching the root
Tree.prototype.search=function(val){
constfound=this.root.search(val)
if(found!==null){
returnfound.value
}
// not found
returnnull
}

// Add a new value to the tree
Tree.prototype.addValue=function(val){
constn=newNode(val)
if(this.root===null){
this.root=n
}else{
this.root.addNode(n)
}
}

// remove a value from the tree
Tree.prototype.removeValue=function(val){
// remove something if root exists
this.root=this.root&&this.root.removeNode(val)
}

// returns the constructor
returnTree
})()

export{Tree}