-
Notifications
You must be signed in to change notification settings - Fork 97
/
traversal.go
39 lines (36 loc) · 1.26 KB
/
traversal.go
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
// Copyright (c) 2016, Peter Mrekaj. All rights reserved.
// Use of this source code is governed by a MIT-style
// license that can be found in the LICENSE.txt file.
package btrees
// InorderTraversal traverse the left subtree, visit the root, then traverse the right subtree.
// The time complexity is O(n), and O(1) additional space is needed.
func InorderTraversal(tree *BTreeP) (w []interface{}) {
var prev, next *BTreeP
for curr := tree; curr != nil; prev, curr = curr, next {
switch prev {
case curr.parent: // Going down: we came down to curr from prev.
if curr.left != nil { // Go left 'til it is possible.
next = curr.left
} else {
w = append(w, curr.Data)
// check and go to the right if the curr.right subtree is not empty. Otherwise go to the curr.parent.
if curr.right != nil {
next = curr.right
} else {
next = curr.parent
}
}
case curr.left: // Going up: previously processed is the left child of current.
w = append(w, curr.Data)
// check and go to the right if the curr.right subtree is not empty. Otherwise go to the curr.parent.
if curr.right != nil {
next = curr.right
} else {
next = curr.parent
}
default: // Done with both children, now go up.
next = curr.parent
}
}
return w
}