FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
Go/structure/binarysearchtree/bstree.go at master · gitgitcode/Go · GitHub
gitgitcode
/
Go
Public
forked from
TheAlgorithms/Go
Notifications
You must be signed in to change notification settings
Fork
0
Star
0
Code
Pull requests
0
Actions
Projects
Security and quality
0
Insights
Additional navigation options
Code
Pull requests
Actions
Projects
Security and quality
Insights
Expand file tree
Breadcrumbs
Go
/
structure
/
binarysearchtree
/
bstree.go
Copy path
More file actions
More file actions
Latest commit
History
History
History
179 lines (160 loc) · 3.77 KB
Breadcrumbs
Go
/
structure
/
binarysearchtree
/
bstree.go
Copy path
File metadata and controls
179 lines (160 loc) · 3.77 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
package
binarytree
// BSTree Returns a binary search tree structure which contains only a root Node
type
BSTree
struct
{
Root
*
Node
}
// calculateDepth helper function for BSTree's depth()
func
calculateDepth
(
n
*
Node
,
depth
int
)
int
{
if
n
==
nil
{
return
depth
}
return
Max
(
calculateDepth
(
n
.
left
,
depth
+
1
),
calculateDepth
(
n
.
right
,
depth
+
1
))
}
// Insert a value in the BSTree
func
Insert
(
root
*
Node
,
val
int
)
*
Node
{
if
root
==
nil
{
return
NewNode
(
val
)
}
if
val
<
root
.
val
{
root
.
left
=
Insert
(
root
.
left
,
val
)
}
else
{
root
.
right
=
Insert
(
root
.
right
,
val
)
}
return
root
}
// Depth returns the calculated depth of a binary saerch tree
func
(
t
*
BSTree
)
Depth
()
int
{
return
calculateDepth
(
t
.
Root
,
0
)
}
// InOrderSuccessor Goes to the left
func
InOrderSuccessor
(
root
*
Node
)
*
Node
{
cur
:=
root
for
cur
.
left
!=
nil
{
cur
=
cur
.
left
}
return
cur
}
// BstDelete removes the node
func
BstDelete
(
root
*
Node
,
val
int
)
*
Node
{
if
root
==
nil
{
return
nil
}
if
val
<
root
.
val
{
root
.
left
=
BstDelete
(
root
.
left
,
val
)
}
else
if
val
>
root
.
val
{
root
.
right
=
BstDelete
(
root
.
right
,
val
)
}
else
{
// this is the node to delete
// node with one child
if
root
.
left
==
nil
{
return
root
.
right
}
else
if
root
.
right
==
nil
{
return
root
.
left
}
else
{
n
:=
root
.
right
d
:=
InOrderSuccessor
(
n
)
d
.
left
=
root
.
left
return
root
.
right
}
}
return
root
}
// InOrder add's children to a node in order left first then right recursively
func
inOrderRecursive
(
n
*
Node
,
traversal
*
[]
int
) {
if
n
!=
nil
{
inOrderRecursive
(
n
.
left
,
traversal
)
*
traversal
=
append
(
*
traversal
,
n
.
val
)
inOrderRecursive
(
n
.
right
,
traversal
)
}
}
// Travers the tree in the following order left --> root --> right
func
InOrder
(
root
*
Node
) []
int
{
traversal
:=
make
([]
int
,
0
)
inOrderRecursive
(
root
,
&
traversal
)
return
traversal
}
// PreOrder Preorder
func
preOrderRecursive
(
n
*
Node
,
traversal
*
[]
int
) {
if
n
==
nil
{
return
}
*
traversal
=
append
(
*
traversal
,
n
.
val
)
preOrderRecursive
(
n
.
left
,
traversal
)
preOrderRecursive
(
n
.
right
,
traversal
)
}
// Travers the tree in the following order root --> left --> right
func
PreOrder
(
root
*
Node
) []
int
{
traversal
:=
make
([]
int
,
0
)
preOrderRecursive
(
root
,
&
traversal
)
return
traversal
}
// PostOrder PostOrder
func
postOrderRecursive
(
n
*
Node
,
traversal
*
[]
int
) {
if
n
==
nil
{
return
}
postOrderRecursive
(
n
.
left
,
traversal
)
postOrderRecursive
(
n
.
right
,
traversal
)
*
traversal
=
append
(
*
traversal
,
n
.
val
)
}
// Travers the tree in the following order left --> right --> root
func
PostOrder
(
root
*
Node
) []
int
{
traversal
:=
make
([]
int
,
0
)
postOrderRecursive
(
root
,
&
traversal
)
return
traversal
}
// LevelOrder LevelOrder
func
levelOrderRecursive
(
root
*
Node
,
traversal
*
[]
int
) {
var
q
[]
*
Node
// queue
var
n
*
Node
// temporary node
q
=
append
(
q
,
root
)
for
len
(
q
)
!=
0
{
n
,
q
=
q
[
0
],
q
[
1
:]
*
traversal
=
append
(
*
traversal
,
n
.
val
)
if
n
.
left
!=
nil
{
q
=
append
(
q
,
n
.
left
)
}
if
n
.
right
!=
nil
{
q
=
append
(
q
,
n
.
right
)
}
}
}
func
LevelOrder
(
root
*
Node
) []
int
{
traversal
:=
make
([]
int
,
0
)
levelOrderRecursive
(
root
,
&
traversal
)
return
traversal
}
// AccessNodesByLayer Function that access nodes layer by layer instead of printing the results as one line.
func
AccessNodesByLayer
(
root
*
Node
) [][]
int
{
var
res
[][]
int
if
root
==
nil
{
return
res
}
var
q
[]
*
Node
var
n
*
Node
var
idx
=
0
q
=
append
(
q
,
root
)
for
len
(
q
)
!=
0
{
res
=
append
(
res
, []
int
{})
qLen
:=
len
(
q
)
for
i
:=
0
;
i
<
qLen
;
i
++
{
n
,
q
=
q
[
0
],
q
[
1
:]
res
[
idx
]
=
append
(
res
[
idx
],
n
.
val
)
if
n
.
left
!=
nil
{
q
=
append
(
q
,
n
.
left
)
}
if
n
.
right
!=
nil
{
q
=
append
(
q
,
n
.
right
)
}
}
idx
++
}
return
res
}
// Max Function that returns max of two numbers - possibly already declared.
func
Max
(
a
,
b
int
)
int
{
if
a
>
b
{
return
a
}
return
b
}
Back
|
FazBrowse Home
|
New Git URL